R-Version: [Default] [32-bit] C:\Program Files\R\R-4.1.0

In folgendem Notebook werden anhand des ‘Movielens’ Datensatzes aus dem Paket RecommenderLab verschiedene Recommender erstellt. Es werden verschiedene Recommender und verschiedene Ähnlichkeiten verwendet, um diese zu vergleichen und auszuwerten. Ziel ist es, ein möglichst guter Recommender zu erstellen und zu verstehen wie dieser funktioniert. Zudem soll verstanden werden wie dieser bewertet wird und was in diesem Falle ein ‘guter’ Recommender bedeutet.

Dieses Notebook konzentriert sich auf Erkenntnisse von Auswertungen und Vergleichen. Um eine Bessere Übersicht zu erhalten wurden grosse sich widerholende Codes in einem ‘helper.R’ file ausgelagert.


data wrangling

# Daten importieren
data(MovieLense)

# dataframe erstellen
movies <- as(MovieLense, "data.frame")
movies <- movies %>% mutate_if(is.character, as.factor)

# breite version des dataframe erstellen
movies_wider <- pivot_wider(
  movies,
  id_cols = user,
  names_from = item,
  values_from = rating,
  values_fill = NULL,
)

Explorative Datenanalyse

df_1 <- movies %>% group_by(item) %>%  summarize(mean_rating = mean(rating)) %>% sample_n(15) %>% arrange(desc(mean_rating))

ggplot(df_1, aes(y = reorder(item, +mean_rating), x = mean_rating)) +
  geom_col(alpha = 1, fill = 'steelblue') +
  scale_y_discrete(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  geom_text(aes(label=round(mean_rating,2)), hjust = 1.3, color = 'white') +
  labs(
    title = "Durchschnittliche Filmbewertung",
    subtitle = "Zufällige Stichprobe von 15 Filmen",
    y = element_blank(),    x = "Dirchschnittlich Bewertung in Sternen"
  ) +
  theme_classic() +
  theme(axis.text.x = element_blank(),
        axis.ticks.x = element_blank(),
        axis.line.x = element_blank(),
        text = element_text(size = 12) # text size
  )

Um einen ersten Überblick über die Daten zu erhalten wurde hier ein Plot von 15 zufällig gewählten Filmen samt der Durchschnittsbewertung geplottet.


1. Welches sind die am häufigsten geschauten Genres / Filme?

movies_genre <- MovieLenseMeta %>%
  rename(item = title)
movies_genre$url <- NULL
movies_genre[movies_genre == 0] <- NA
a <- which(movies_genre==1,arr.ind=TRUE)
movies_genre[a] <- names(movies_genre)[a[,"col"]]
movies_genre <- movies_genre %>%
  unite("genres", unknown:Western, sep= ",", 
        remove = TRUE, na.rm = TRUE)
genres<-merge(x=movies,y=movies_genre,by="item",all.x=TRUE)%>%
  mutate(genres = strsplit(as.character(genres), ",")) %>%
  unnest(genres)

df1a <- movies%>%
  group_by(item)%>%
  summarize(count=n())%>%
  ungroup()%>%
  arrange(desc(count))

df1a <- head(df1a, 10)

df1a %>%
  mutate(item = fct_reorder(item, count))%>%
  ggplot(aes(x = count, y = item))+
  geom_col(alpha = 1, fill = 'steelblue')+
  scale_y_discrete(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  geom_text(aes(label=round(count,2)), hjust = 1.3, color = 'white') +
  labs(
    title = "Meist bewertete Filme",
    y = element_blank(),    x = "Anzahl Bewertungen"
  ) +
  theme_classic() +
  theme(axis.text.x = element_blank(),
        axis.ticks.x = element_blank(),
        axis.line.x = element_blank(),
        text = element_text(size = 12) # text size
  )

Da in unserem Datensatz nur die Anzahl Ratings von Filmen gegeben ist, gehen wir davon aus, dass die meist bewerteten, auch die am meist geschauten Filme sind. In der Grafik sieht man die 10 meist bewerteten Filme.

df1b <- genres%>%
  group_by(genres)%>%
  summarize(count=n())%>%
  ungroup()%>%
  arrange(desc(count))

df1b%>%
  mutate(genres = fct_reorder(genres, count))%>%
  ggplot(aes(x = count, y = genres))+
  geom_col(alpha = 1, fill = 'steelblue')+
  geom_text(aes(label=round(count,2)), hjust = -0.2, color = 'black') +
  scale_y_discrete(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0), limits = c(0,45000)) +
  geom_text(aes(label=count,2), hjust = 1.3, color = 'white') +
  labs(
    title = "Meist bewertete Genres",
    y = element_blank(),    x = "Anzahl Bewertungen"
  ) +
  theme_classic() +
  theme(axis.text.x = element_blank(),
        axis.ticks.x = element_blank(),
        axis.line.x = element_blank(),
        text = element_text(size = 12) # text size
  )

Auch hier wird davon ausgegangen, dass die enres, welche am häufigsten bewertet wurden auch am häufigst geschaut wurden. In der Grafik ist zu sehen, dass Drama das top Genres ist, gefolgt von Comedy und Action.


2. Wie verteilen sich die Kundenratings gesamthaft und nach Genres?

ggplot(movies, aes(x = rating)) +
  geom_bar(alpha = 1, fill = 'steelblue') +
  geom_text(stat='count', aes(label=..count..), vjust=1.5, color = 'white') +
  scale_y_continuous(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  labs(
    title = "Verteilung Kundenratings gesamthaft",
    subtitle = paste("N = ", nrow(movies), " Bewertungen"),
    x = "Kundenbewertungen", 
    y = "Anzahl",
    fill = element_blank()
  ) +
  theme_classic() +
  theme(
    text = element_text(size = 12)
  )

In dieser Grafik ist die Verteilung der bewertungen zu sehen. Die Bewertungen 4 und 5 wirden klar am häufigsten vergeben, wobei 1 und 2 eher selten bewertet werden.

# get rating count per user, add as column for further processing
counts <- movies %>% group_by(user) %>% count()
movies2 <- merge(movies, counts, by="user")
movies_wider2 <- merge(movies_wider, counts, by="user")

# avoid users with almost no ratings, use median as threshold
median_count <- median(counts$n)

# get sample
set.seed(623)
movies_sample <- movies_wider2 %>% filter(n > median_count) %>% sample_n(5)

# create long table
movies_sample_long <- filter(movies2, user %in% movies_sample$user)

# drop item names, 
movies_sample_long <- subset(movies_sample_long, select = -c(item))

df2b <- genres%>%
  group_by(genres)
  
movies_sample_long_grouped <- movies_sample_long %>% group_by(user, rating) %>% summarise(rating_dens = length(user) / first(n), user = first(user), n=first(n), rating = first(rating))
  
ggplot(genres, aes(x = rating, fill = genres)) +
  geom_bar(alpha = 1, bins = 10) +
  facet_wrap(~genres)+
  scale_y_continuous(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  labs(
    title = "Verteilung Kundenratings nach Genres",
    subtitle = paste("N = ", nrow(movies), " Bewertungen"),
    x = "Durchschnittliche Bewertung", 
    y = "Anzahl",
    fill = element_blank()
  ) +
  theme(
    text = element_text(size = 12),
    legend.position = 'none'
  )

Hier ist zu sehen, dass das Genres Drama am meisten bewertet wurde, wobei Dokumentationen am wenigsten Bewertungen erhalten haben. Die Bewertungen pro Genres verteilen sich jeweils sehr ähnlich. Die Verteilungen der einzelnen Genres sind ebenfalls ähnlich verteilt wie die bewertungen gesamthaft.


3.Wie verteilen sich die mittleren Kundenratings pro Film?

df3 <- movies %>% 
  group_by(item) %>%  
  summarize(
    mean_rating = mean(rating),
    ratings = n()
  ) %>% 
  mutate(
    more_than_50 = ifelse(ratings >= 50, 'b) mehr als 50 Bewertungen', 'a) weniger als 50 Bewertugen')
  )

ggplot(df3, aes(x = mean_rating)) +
  geom_histogram(alpha = 1, fill = 'steelblue', binwidth = 0.06) +
  scale_y_continuous(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  labs(
    title = "Verteilung mittlere Kundenratings pro Film",
    subtitle = paste("N = ", nrow(movies), " Bewertungen"),
    x = "Durchschnittliche Bewertung", 
    y = "Dichte"
  ) +
  theme_classic() +
  theme(text = element_text(size = 12)
  )

In dieser Grafik ist die durchschnittliche Bewertung pro Film zu sehen, wobei auch hier zu sehen ist ,dass die die meisten Filme eine Durchschnittliche Bewertung von ca. 3 - 3.5 haben. Auffällig ist, dass bei den distinkten Werten (1, 2, 3, 4, & 5) aussreisser zu erkennen sind. Dies liegt an Filmen,welche nur wenige male oder nur einmal bewertet wurden.

ggplot(df3, aes(x = mean_rating, fill = more_than_50)) +
  geom_density(alpha = 0.5, bw = 0.08) +
  scale_y_continuous(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  labs(
    title = "Verteilung mittlere Kundenratings pro Film",
    subtitle = "N = 1664 Filme",
    x = "Durchschnittliche Bewertung", 
    y = "Dichte",
    fill = element_blank()
  ) +
  theme_classic() +
  theme(
    text = element_text(size = 12),
    legend.position = 'bottom'
  )

TODO: N = Anzahl bewertungen für Kategorie a & b

Für diese Grafik wurden die Filme in zwei gruppen unterteilt: Filme die weniger als 50 bewertungen erhalten haben, und Filme welche mehr als 50 Bewertungen erhalten haben. In der Grafik ist imernoch die durchschnittliche Bewertung dieser Filme zu sehen wobei deutlich erkannt werden kann, dass filme welche weniger bewertungen erhalten haben, tendenziell auch schlechter bewertet wurden.


4.Wie stark streuen die Ratings von individuellen Kunden?

# Number of ratings per user per rating value
movies_sample_long_grouped <- movies_sample_long %>% group_by(user, rating) %>% summarise(rating_dens = length(user) / first(n), user = first(user), n=first(n), rating = first(rating))

movies_span <- movies %>% group_by(user) %>% 
  summarize(mean = mean(rating), min = min(rating), max = max(rating), span = (max(rating) - min(rating)))

set.seed(123)

ggplot(movies_span  %>% group_by(span) %>% summarise(count = n()), aes(x=span, y=count)) +
  geom_col(fill = 'steelblue') +
  scale_y_continuous(limits = c(0,800), expand = c(0,0)) +
  geom_text(aes(label=round(count,2)), vjust = -0.7, color = 'black') +
  labs(
    title = "Spannweite Kundenratings",
    subtitle = "",
    x = "Spannweite", 
    y = "Anzahl User"
  )+
    theme_classic() + 
  theme(
    text = element_text(size = 12),
    legend.position = 'bottom'
  )

In diesen Grafiken sehen wir detailliertere Informationen über die Spannweite und den Mittelpunkt. In der ersten Übersicht ist die Spannweite und der Mittelpunkt einzelner Kunden dargestellt. Es fällt auf, dass trotz des teilweise relativ hohem Mittelwert alle Ratings von 1-5 abgegeben wurden. Ein rating von 5 wurde sozusagen immer abgegeben, 1 nicht immer. In der zweiten Übersicht ist die Spannweite aller Kunden dargestellt. Hier wird sichtbar, dass die meisten Kunden Bewertungen von 1-5 abgegeben haben (Spannweite=4), und nur weinige sehr homogen bewertet haben (Spannweite = 1-2). Eine kleine Spannweite kann hier auch aufgetreten sein, da diese User sehr wenige Bewertungen abgegeben haben.


5.Welchen Einfluss hat die Normierung der Ratings pro Kunde auf deren Verteilung?

movies_sample_long_grouped <- movies %>% group_by(rating) %>% summarise(rating_dens = n())

ggplot(movies_sample_long_grouped, aes(x=rating, y = rating_dens)) + 
  geom_col(fill = 'steelblue') +
  scale_y_continuous(expand = c(0,0)) +
  geom_text(aes(label=round(rating_dens,2)), vjust = 1.5, color = 'white') +
  labs(
    title = "Häufigkeit der Kundenbewertungen",
    subtitle = paste("N =",  nrow(movies), " Bewertungen"),
    x = "User Bewertung (1-5)", 
    y = "Anzahl Bewertungen",
    fill = element_blank()
  ) +
  scale_fill_manual("legend", values = c("cyan3", "cyan4", "darkolivegreen3", "darkolivegreen", "coral4")
                    )+
  theme_classic() + 
  theme(
    text = element_text(size = 12),
    legend.position = 'bottom'
  )

MovNorm <- normalize(MovieLense, method="Z-score")
mov <- as(MovNorm, "data.frame")

ggplot(mov, aes(x=rating)) + 
  geom_histogram(fill = 'steelblue', bins = 70) +
  scale_y_continuous(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  labs(
    title = "Häufigkeit der Kundenbewertungen",
    subtitle = paste("N = ", nrow(mov), "Bewertungen"),
    x = "User Bewertung Normiert", 
    y = "Anzahl Bewertungen",
    fill = element_blank()
  ) +
  scale_fill_manual("legend", values = c("cyan3", "cyan4", "darkolivegreen3", "darkolivegreen", "coral4")
                    )+
  theme_classic() + 
  theme(
    text = element_text(size = 12),
    legend.position = 'bottom'
  )

Die Ratings sind nun ungefähr Normalverteilt mit einem Durchschnittsrating von 0 und einer Standardabweichung von 1. Erkennbar ist, dass die Verteilung rechtssteil und linksschief ist, also mehrheitlich positive Bewertungen abgegeben wurden. Durch die Normierung der Daten werden die Ratings jedes Users auf dieselbe Verteilung gestaucht, wodurch man die Verteilung aller Daten analysieren kann. Dadurch hat man beispielsweise die Möglichkeit die durchschnittliche Bewertungstendenz herauszufinden.


6.Welche strukturellen Charakteristika (z.B. Sparsity) und Auffälligkeiten zeigt die User Item Matrix?

image(as(MovieLense, "dgCMatrix"))

In dieser Grafik werden werden die Bewertungen von Users (Row) den Filmen (Column) gegenübergestellt. Die Achsenbeschriftung konnte nicht besser speizifiziert werden.

Users mit tiefen ID’s und Filme mit hohen ID’s weisen weniger ratings auf. Filme mit tiefer ID jedoch sehr viele. Dies erklärt die nicht vorhandenen Datenpunkte in der Grafik oben rechts Auffallend ist, dass es einige wenige User gibt, die fast alle Filme bewertet haben (erkennbar durch die horizontalen scharzen Striche). Dies scheinen sehr aktive Bewerter zu sein. Viele Users haben jedoch nur einen kleinen Teil der Filme bewertet. Bei den Filmen ist eine ähnliche Tendenz wahrzunehmen, jedoch sind die vertikalen Striche breiter. Möglicherweise sind dort einige beliebte Filme zusammengefasst.

sparcity <- sum(is.na(movies_wider[,-1])) / prod(dim(movies_wider))
sparcity
[1] 0.9360962

TODO: nur 6.4% der Daten haben Values / sind non NA’s- ein User hat im durchschnitt 6.4% der Filme bewertet -> schöner schreiben

Die Matrix ist sehr sparce. Fast 94% der Daten bestehen aus NA Werten. Dies wurde so erwartet, da es unwahrscheinlich ist dass ein Film von allen users akiv bewertet wird, oder dass ein User alle Filme ansieht und auch bewertet.


Datenreduktion

#Data reduction
dense_reduction <- data_reduction_dense(MovieLense)
dense_user_reduction <- data_reduction_dense_user(MovieLense)
random_reduction <- data_reduction_random(MovieLense)

#same as dense reduction
ratingMatrix <- data_reduction_dense(MovieLense)

matrices <- c('Original Matrix (MovieLense)', 'dense_reduction', 'dense_user_reduction', 'random_reduction')
sparsities <- c(get_sparsity(MovieLense), get_sparsity(dense_reduction), get_sparsity(dense_user_reduction), get_sparsity(random_reduction))

df_sparsity <- data.frame(matrix = matrices, sparsity = sparsities)

#Plot Data reduction
ggplot(df_sparsity, aes(x=matrix, y = sparsity)) + 
  geom_col(fill = 'steelblue') +
  coord_flip() +
  scale_y_continuous(expand = c(0,0)) +
  geom_text(aes(label=round(sparsity,2)), hjust = 1.3, color = 'white') +
  labs(
    title = "Sparsity der verschiedenen Datenreduktionen",
    x = element_blank(), 
    y = "Sparcity in Prozent",
    fill = element_blank()
  ) +
  theme_classic() + 
  theme(
    text = element_text(size = 12),
    legend.position = 'bottom'
  )

TODO: Besserer beschreib zu den reduktionen - wieso welche reduktionen + wieso diese sparcity Für die dense_reduction sinkt die Sparsity von 93.67% auf 75.80%. Für die dense_user_reduction sinkt die Sparsity von 93.67% auf 88.18%. Für die random_reduction bleibt die Sparsity praktisch unverändert. Sie sinkt von 93.67% auf 92.75%.

p1 <- image(dense_reduction, main = "Raw Ratings for Dense Reduction")
p2 <- image(dense_user_reduction, main = "Raw Ratings for Dense User Reduction")
p3 <- image(random_reduction, main = "Raw Ratings for Random Reduction")

grid.arrange(p1, p2, p3, ncol = 3, nrow = 1)

TODO: mehr beschreibung

Man sieht sehr klar, dass die matrix nun deutlich weniger sparse ist.

p1 <- show_change_of_rating_distribution(MovieLense, dense_reduction, 'Für dense_reduction, N alte Matrix = 1664 Filme, N neue Matrix = 700 Filme')
p2 <- show_change_of_rating_distribution(MovieLense, dense_user_reduction, 'Für dense_user_reduction, N alte Matrix = 1664 Filme, N neue Matrix = 700 Filme')
p3 <- show_change_of_rating_distribution(MovieLense, random_reduction, 'Für random_reduction, N alte Matrix = 1664 Filme, N neue Matrix = 700 Filme')

grid.arrange(p1, p2, p3, ncol = 2, nrow = 2)

TODO: beschreibung


Analyse Ähnlichkeitsmatrix

1. Zerlege den reduzierten MovieLense Datensatz in ein disjunktes Trainings- und Testdatenset im Verhältnis 4:1

#both <- split_dataset(ratingMatrix, 0.8)
#train <- both[[1]]
#test <- both[[2]]

#print('Trainingsdatenset:')
#dim(train)
#print('')
#print('Testdatenset:')
#dim(test)

e <- evaluationScheme(dense_reduction, method="split", train=0.8, k=1, given=0)
The following users do not have enough items leaving no given items: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400
train <- getData(e, "train")
test <- getData(e, 'unknown')

TODO: ignore warning + evtl. löschen?


2. Trainiere ein IBCF Modell mit 30 Nachbarn und Cosine Similarity

# train IBCF recommender
rec <- Recommender(train, method = "IBCF", param=list(method="Cosine", k=30, normalize = NULL, na_as_zero = TRUE)) #normalize = 'center'
# predict top 10 movies for 100 users
pre <- predict(rec, test, n = 10)

3. Bestimme die Verteilung der Filme, welche bei IBCF für paarweise Ähnlichkeitsvergleiche verwendet werden

model <- getModel(rec)
colSum <- colSums(model$sim > 0)

df <- as.data.frame(colSum)

# add index column
df <- cbind(item = rownames(df), df)
rownames(df) <- 1:nrow(df)

ggplot(df, aes(x = colSum)) +
  geom_histogram(alpha = 1, fill = 'steelblue', binwidth = 2) +
  scale_y_continuous(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  labs(
    title = "Verteilung der Anzahl ähnlicher Filme",
    # subtitle = paste("N = ", nrow(df3), " Filme"),
    x = "Anzahl Filme bei denen der Film als Nachbar auftaucht", 
    y = "Häufigkeit"
  ) +
  theme_classic() +
  theme(text = element_text(size = 12)
  )

TODO: gute beschreibung


4. Bestimme die Filme, die am häufigsten in der Cosine-Ähnlichkeitsmatrix auftauchen und analysiere deren Vorkommen und Ratings im reduzierten Datensatz

df1 <- df %>% arrange(desc(colSum)) %>% head(10)

ggplot(df1, aes(x = colSum, y = reorder(item, +colSum)))+
  geom_col(alpha = 1, fill = 'steelblue')+
  scale_y_discrete(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  geom_text(aes(label=round(colSum,2)), hjust = 1.3, color = 'white') +
  labs(
    title = "Häufigste Filme in Cosine-Ähnlichkeitsmatrix",
    y = element_blank(),
    x = "Anzahl Filme in deren Nachbarschaft der Film ist"
  ) +
  theme_classic() +
  theme(axis.text.x = element_blank(),
        axis.ticks.x = element_blank(),
        axis.line.x = element_blank(),
        text = element_text(size = 12) # text size
  )

TODO: Beschreibung

top10 <- as.list(df1)$item

data <- as(ratingMatrix, "data.frame")
data1 <- data %>%
  group_by(item) %>%
  summarize(mean_rating = mean(rating)) %>%
  arrange(desc(mean_rating)) %>%
  mutate(category = ifelse(item %in% top10, 'Häufigste 10 Filme', 'Restliche Filme'))

ggplot(data1, aes(x = mean_rating, fill = category)) +
  geom_density(alpha = 0.5, bw = 0.05) +
  scale_y_continuous(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  labs(
    title = "Verteilung mittlere Kundenratings pro Film",
    x = "Durchschnittliche Bewertung",
    y = "Dichte",
    fill = element_blank()
  ) +
  theme_classic() +
  theme(
    text = element_text(size = 12),
    legend.position = c(.14, .93)
  )

TODO: mehr beschreibung Es fällt auf, dass die häufigsten Filme allgemein sehr gut bewertet werden.


##Analyse Top-N Listen - IBCF vs. UBCF ####1.Berechne Top-15 Empfehlungen für Testkunden mit IBCF und UBCF

rec_ibcf <- Recommender(train, method = "IBCF", param=list(method="Cosine", k=30, normalize = NULL, na_as_zero = TRUE))
topn_ibcf <- predict(rec_ibcf, test, n = 15)
topn_ibcf_list <- as(topn_ibcf, "list")
topn_ibcf_df <- as.data.frame(do.call(rbind, topn_ibcf_list))

rec_ubcf <- Recommender(train, method = "UBCF", param=list(method="Cosine", normalize = NULL))
topn_ubcf <- predict(rec_ubcf, test, n = 15)
topn_ubcf_list <- as(topn_ubcf, "list")
topn_ubcf_df <- as.data.frame(do.call(rbind, topn_ubcf_list))

####2.Vergleiche die Top-15 Empfehlungen und deren Verteilung und diskutiere Gemeinsamkeiten und Unterschiede zwischen IBCF und UBCF für alle Testkunden.

#compare most occurring items

ibcf_top <- head(sort(colCounts(topn_ibcf), decreasing = TRUE))
ibcf_top_df <- as.data.frame(ibcf_top)
ibcf_top_df <- tibble::rownames_to_column(ibcf_top_df, "movies")
names(ibcf_top_df)[names(ibcf_top_df) == 'ibcf_top'] <- 'n_appearances'


ubcf_top <- head(sort(colCounts(topn_ubcf), decreasing = TRUE))
ubcf_top_df <- as.data.frame(ubcf_top)
ubcf_top_df <- tibble::rownames_to_column(ubcf_top_df, "movies")
names(ubcf_top_df)[names(ubcf_top_df) == 'ubcf_top'] <- 'n_appearances'

p1 <- plot_most_occ_item(ibcf_top_df, 'ibcf')
p2 <- plot_most_occ_item(ubcf_top_df, 'ubcf')

grid.arrange(p1, p2, ncol = 2, nrow = 1)

Auffällig ist, dass im UBCF die Filme, welche am häufigsten in den Top-15 Empfehlungen auftauchen, wesentlich öfters vorkommen als diese, die im IBCF als am meist vorkommende Filme definiert sind. Ebenfalls auffallend ist, dass die beiden Recommender sehr verschiedene Vorschläge machen. Für die meist vorkommenden Filme in den TopNListen gibt es hier keine Überschneidung.

#get distribution of intersect for each user
#intersect of top 15 recommendations IBCF vs UBCF
#list_comp_ibcf_ubcf <- vector(mode = "list", length = length(topn_ibcf_list))
list_comp_ibcf_ubcf <- list()
for (n in 1:length(topn_ibcf_list)) {
  intersection <- length(intersect(unlist(topn_ibcf_list[n]), unlist(topn_ubcf_list[n]))) / 15
  list_comp_ibcf_ubcf <- append(list_comp_ibcf_ubcf, intersection)
}

comp_ibcf_ubcf <- data.frame(matrix(unlist(list_comp_ibcf_ubcf), nrow=length(list_comp_ibcf_ubcf), byrow=TRUE))
colnames(comp_ibcf_ubcf) <- c('intersect')
comp_ibcf_ubcf <- comp_ibcf_ubcf %>% group_by(intersect) %>% summarise(count = n()) %>% ungroup()
comp_ibcf_ubcf$intersect <- as.character(round(comp_ibcf_ubcf$intersect, 2))

ggplot(comp_ibcf_ubcf, aes(x = intersect, y = count)) +
  geom_col(alpha = 1, fill = 'steelblue') +
  geom_text(aes(label=count), vjust=1.5, color = 'white') +
  scale_y_continuous(expand = c(0,0)) +
  labs(
    title = "Verteilung der überschneidung der empfohlenen Filme",
    # subtitle = paste("N = ", nrow(df3), " Filme"),
    x = "Überschneidung in %", 
    y = "Häufigkeit"
  ) +
  theme_classic() +
  theme(text = element_text(size = 12)
  )

TODO: beschreib


Analyse Top-N Listen - Ratings

Vergleiche den Anteil übereinstimmender Empfehlungen der Top-15 Liste für IBCF vs UBCF, beide mit ordinalem Rating und Cosine Similarity für alle Testkunden

#ibcf recommender with Jaccard similarity
rec_ibcf_jac <- Recommender(train, method = "IBCF", param=list(method="Jaccard", k=30, normalize = NULL, na_as_zero = TRUE))
topn_ibcf_jac <- predict(rec_ibcf_jac, test, n = 15)
topn_ibcf_jac_list <- as(topn_ibcf_jac, "list")

#ubcf recommender with Jaccard similarity
rec_ubcf_jac <- Recommender(train, method = "UBCF", param=list(method="Jaccard", normalize = NULL))
topn_ubcf_jac <- predict(rec_ubcf_jac, test, n = 15)
topn_ubcf_jac_list <- as(topn_ubcf_jac, "list")

comparison <- matrix(ncol = 2, nrow = 3)

#intersect of top 15 recommendations IBCF vs UBCF cosine similarity
comp_ord_cos<- 0
for (n in 1:length(topn_ibcf_list)) {
  intersection <- length(intersect(unlist(topn_ibcf_list[n]), unlist(topn_ubcf_list[n]))) / 15
  comp_ord_cos <- comp_ord_cos + intersection
}
comparison[1,1] <- 'ibcf cos - ubcf cos'
comparison[1,2] <- round(comp_ord_cos / length(topn_ibcf_list), 2)


#intersect of top 15 recommendations IBCF vs UBCF Jaccard similarity
comp_bin_jac<- 0
for (n in 1:length(topn_ibcf_jac_list)) {
  intersection <- length(intersect(unlist(topn_ibcf_jac_list[n]), unlist(topn_ubcf_jac_list[n]))) / 15
  comp_bin_jac <- comp_bin_jac + intersection
}
comparison[2,1] <- 'ibcf cos - ubcf jac'
comparison[2,2] <- round(comp_bin_jac / length(topn_ibcf_jac_list), 2)

#intersect of top 15 recommendations UBCF Cosine Similarity vs UBCF Jaccard similarity
comp_cos_jac<- 0
for (n in 1:length(topn_ubcf_jac_list)) {
  intersection <- length(intersect(unlist(topn_ubcf_jac_list[n]), unlist(topn_ubcf_list[n]))) / 15
  comp_cos_jac <- comp_cos_jac + intersection
}
comparison[3,1] <- 'ubcf cos - ubcf jac'
comparison[3,2] <- round(comp_cos_jac / length(topn_ubcf_jac_list), 2)

comparison <- data.frame(comparison)
comparison

ggplot(comparison, aes(x = X1, y = X2)) +
  geom_col(alpha = 1, fill = 'steelblue') +
  #geom_text(aes(label=count), vjust=1.5, color = 'white') +
  scale_y_discrete(expand = c(0,0)) +
  labs(
    title = "Verteilung der überschneidung der empfohlenen Filme",
    # subtitle = paste("N = ", nrow(df3), " Filme"),
    x = "Überschneidung in %", 
    y = "Häufigkeit"
  ) +
  theme_classic() +
  theme(text = element_text(size = 12)
  )

TODO: ForLoop TODO: für alle Datenreduktionen + 3 plots in grid (width = 15)


##Analyse Top-N Listen - IBCF vs SVD ####1.Vergleiche wie sich der Anteil übereinstimmender Empfehlungen der Top-15 Liste für IBCF vs verschiedene SVD Modelle verändert, wenn die Anzahl der Singulärwerte für SVD von 10 auf 20, 30, 40, 50 verändert wird

#dense_reduction, dense_user_reduction, random_reduction

datasets = c(dense_reduction, dense_user_reduction, random_reduction)
datasetnames = c('dense_reduction', 'dense_user_reduction', 'random_reduction')
k = c(10, 20, 30, 40, 50)
dense_reduction
400 x 700 rating matrix of class ‘realRatingMatrix’ with 67765 ratings.
output <- data.frame('comparison' = character(), 'intersection' = numeric(), 'dataset' = character())
colnames(output) <- c('comparison', 'intersection', 'dataset')

for (d in 1:length(datasets)){
  e <- evaluationScheme(datasets[[d]], method="split", train=0.8, k=1, given=0)
  train <- getData(e, "train")
  test <- getData(e, 'unknown')
  
  for (n in k){
    rec_svd <- Recommender(train, method = "SVD", param=list(k = n))
    topn_svd <- predict(rec_svd, test, n = 15)
    topn_svd_list <- as(topn_svd, "list")
  
    comp_ibcf_svd <- 0
    for (i in 1:length(topn_ibcf_list)) {
      intersection <- length(intersect(unlist(topn_ibcf_list[i]), unlist(topn_svd_list[i]))) / 15
      comp_ibcf_svd <- comp_ibcf_svd + intersection
    }
    out <- c(paste('IBCF vs. SVD', n), round(comp_ibcf_svd / length(topn_ibcf_list), digits = 4), as.character(datasetnames[[d]]))
    output[nrow(output) + 1,] = out
    }
}
The following users do not have enough items leaving no given items: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400The following users do not have enough items leaving no given items: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400The following users do not have enough items leaving no given items: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400
output

ggplot(output, aes(x = comparison, y = intersection, fill = dataset)) +
  geom_col(alpha = 1, position = position_dodge()) +
  #geom_text(aes(label=count), vjust=1.5, color = 'white') +
  scale_y_discrete(expand = c(0,0)) +
  labs(
    title = "Verteilung der überschneidung der empfohlenen Filme",
    # subtitle = paste("N = ", nrow(df3), " Filme"),
    x = "Überschneidung in %", 
    y = "Häufigkeit"
  ) +
  theme_classic() +
  theme(text = element_text(size = 12),
        axis.text.x = element_text(angle = 60, hjust = 1)
  )

TODO: beschreib


Wahl des optimalen Recommenders

Verwende für die Evaluierung 10-fache Kreuzvalidierung,

Als erstes stellte sich die Frage, ob precision, recall, oder ein kombinierter F1-Score als performance Metrik gewählt werden sollte. Precision ist umgekehrt proportional zu false positive, recall zu false negative Voraussagen. Da es in diesem Fall wichtiger ist, die gemachten Empfehlungen korrekt vorauszusagen, wurde Precision als Performance Metrik definiert. Als zweite Wahl würden wir auf den F1-Score zurückggreifen. Dieser setzt sich aus der Kombination beider Petriken precision und recall zusammen.

Der Parameter goodRating stellt die binäre Grenze dar, bei welcher ein rating als “positiv” bezeichnet werden kann. Wird der Wert höher gesetzt, sinkt die precision und der recall steigt. In dieser Modelloptimierung wurde definiert, dass alle Ratings ab 3 als positiv klassiert werden sollten.

In dieser Grafik ist die precision der novelty der trainierten Modelle gegenübergestellt. Dabei wurde jedes Modell für n-recommendations trainiert und dargestellt. Es wurde 10 fold cross validation verwendet. Die dargestellten Werte visualisieren das arithmetische Mittel der Scores auf den jeweils 10 Testdatensätzen. Dadurch können die Modelle und Parameter unabhängig von der Struktur der Daten miteinander verglichen werden.

Als erstes wurde sichtbar, dass die Modellwahl mehr Einfluss auf die precision des Modell hatte als die n-recommendations. Deshalb wurde nur SVD und popular für weitere Hyperparameteroptimierung angeschaut.

Das SVD Modell wurde hier für verschiedene k’s trainiert. Dabei wurde klar, dass ein k~5 die beste precision voraussagt. Jedoch kommt das Modell nicht annähernd an die precision von popular heran.

Das beste daraus resultierende Modell ist in dem Falle “popular items” mit n=10 Voraussagen.

Das popular Modell besitzt keine Hyperparameter für die Optimierung. Deshalb wird hier SVD bezüglich Hyperparameter k und n im Detail optimiert.

Für das Modell SVD ist die Precision am besten, wenn k=4 ist und n=10. Zudem wurde festgestellt, dass je nach Seed Position k=5 besser sein kann. Die precision des Modells mit optimierten Hyperparameter ist immernoch tiefer, als die des popular Modells.


Implementierung Ähnlichkeitsmatrix

Als erstes wird hier ein sample aus 100 zufällig gewähten Filmen gezogen.


# reduce samples to 100 users
sample_sim <- sample_similarity(movies)
# generate matrix equivalent
sample_sim_matrix <- as(sample_sim, 'matrix')
# convert back to real rating matrix
sample_sim_rating <- as(sample_sim, "realRatingMatrix")
sample_sim_rating_norm <- normalize(sample_sim_rating)
sample_sim_wide_norm <- as(sample_sim_rating_norm, 'matrix')
# create wide versionwide version
sample_sim_wide <- pivot_wider(
  sample_sim,
  id_cols = user,
  names_from = item,
  values_from = rating,
  values_fill = NULL,
)

sample_sim_wide

Hier wird hier ein IBCF recommender gebaut, um die cosine similarity Matrix der Filme mithilfe von Recommenderlab zu erstellen. Dabei wurden folgende Parameter eingestellt: - k: in Recommenderlab wird die similarity zu k Nachbaren berechnet. Damit die Implementierung mit der Eigenen überein stimmen kann, muss dieser Wert gleich gross oder grösser als die Anzahl Items in den Daten sein. Da wir 100 Filme ausgewählt haben, wird k=100 gewählt.

k_value = dim(sample_sim_rating)[2]
print(paste("K-Wert: ", k_value))
[1] "K-Wert:  100"
start.time <- Sys.time()
rec <- Recommender(sample_sim_rating, method = "IBCF", param=list(method="Cosine", k=k_value, normalize = NULL, na_as_zero = TRUE))
end.time <- Sys.time()
elapsed.time <- round((end.time - start.time), 3)
print(elapsed.time)
Time difference of 0.08 secs
similarity <- as.matrix(rec@model$sim)
#image(similarity)
plot_sim(similarity)

Es wird sichtbar, dass die Diagonalwerte eine andere Farbe aufweisen. Leider kann man die Similarities aufgrund der Menge von Datenpunkten nicht wirklich vergleichen. Werden die ersten Werte visualisiert, wird jedoch klar dass die Diagonaleinträge 0 anstatt 1 sind. Dies ist jedoch nicht weiter tragisch, da diese Daten keine Informationen tragen. Sie können deshalb ignoriert werden.

similarity[1:3, 1:3]
                                    20,000 Leagues Under the Sea (1954) Ace Ventura: Pet Detective (1994) Airheads (1994)
20,000 Leagues Under the Sea (1954)                           0.0000000                         0.2446432       0.1596641
Ace Ventura: Pet Detective (1994)                             0.2446432                         0.0000000       0.4807474
Airheads (1994)                                               0.1596641                         0.4807474       0.0000000

# sort colums alphabetical without user column indexes
sample_sim_zero <- sample_sim_wide[-1][, order(colnames(sample_sim_wide[-1])),]
# convert to matrix
sample_sim_zero <- as(sample_sim_zero, 'matrix')
# replace nas with 0 (non adjusted cosine similarity)
sample_sim_zero[is.na(sample_sim_zero)] <- 0

start.time <- Sys.time()
cosine_sim_matrix <- cosine_sim2(t(sample_sim_zero), t(sample_sim_zero))
end.time <- Sys.time()
elapsed.time <- round((end.time - start.time), 3)
print(elapsed.time)
Time difference of 0.047 secs
plot_sim(cosine_sim_matrix)

Hier wurde die cosine similarity als Matrix Berechnung implementiert. Der Zeitaufwand der Berechnung ist etwas geringer als bei der Implementierung von Recommenderlab. Dies ist der Fall, da im recommenderlab Package noch weitere Schritte durchlaufen werden, um beispielsweise für k Nachbaren zu optimieren. Wie man erkennen kann, sind die Ausprägungen der Similarities ähnlich zur Recommenderlab Implementierung, bis auf die Diagonalwerte. Diese werden deshalb noch durch 0 ersetzt.

diag(cosine_sim_matrix) <- 0
cosine_sim_matrix[1:3, 1:3]
                                    20,000 Leagues Under the Sea (1954) Ace Ventura: Pet Detective (1994) Airheads (1994)
20,000 Leagues Under the Sea (1954)                           0.0000000                         0.2446432       0.1596641
Ace Ventura: Pet Detective (1994)                             0.2446432                         0.0000000       0.4807474
Airheads (1994)                                               0.1596641                         0.4807474       0.0000000

Auch die ersten Zahlenwerte stimmen mit dem Print der similarities von recommenderlab überein.

Nun werden die Zahlenwerte der zwei berechneten similarity Matrizen verglichen.

sum(abs(cosine_sim_matrix - similarity))
[1] 2.17576e-13

Wie hier sichtbar wird, ist die Summe der absoluten Differenzen aller Werte der Matrizen verschwindend klein. Die Matrizen sind also bis auf den Fliesskommafehler identisch.

Als nächstes wird die jaccard similarity berechnet. Dafür werden die Ratings zuerst binärisiert. Als Splitkriterium wurde ein Rating von 3 gewählt, was bedeutet dass alle Ratings ab 3 als True dargestellt werden, alle Ratings darunter als False.

# binarize matrix and make split at a rating of 3
sample_sim_bin <- as(binarize(as(sample_sim_rating, "realRatingMatrix"), minRating=3), "matrix") * 1

# replace nas with 0 (no adjusted cosine similarity)
#wide_matrix[is.na(wide_matrix)] <- 0

# ibcf, because columns are taken here
# row count

start.time <- Sys.time()
jac_own <- jaccard_sim2(t(sample_sim_bin), t(sample_sim_bin))
end.time <- Sys.time()
elapsed.time <- round((end.time - start.time), 3)
print(elapsed.time)
Time difference of 0.037 secs
plot_sim(jac_own)


#dim(wide_matrix)
jac_own[1:3, 1:3]
                                    20,000 Leagues Under the Sea (1954) Ace Ventura: Pet Detective (1994) Airheads (1994)
20,000 Leagues Under the Sea (1954)                          1.00000000                         0.1120000      0.02631579
Ace Ventura: Pet Detective (1994)                            0.11200000                         1.0000000      0.11842105
Airheads (1994)                                              0.02631579                         0.1184211      1.00000000

Auch bei der Implementierung der Jaccard Similarity ist dank Matriximplementation der Zeitaufwand relativ gering. Hier fällt jedoch auf, dass auf der Diagonalen Lücken bestehen.

print(paste("NA value count in similarity matrix:", sum(is.na(jac_own))))
[1] "NA value count in similarity matrix: 4"
jac_own[43:45, 43:45]
                    Heavyweights (1994) Homage (1995) Houseguest (1994)
Heavyweights (1994)                 1.0             0               0.1
Homage (1995)                       0.0           NaN               0.0
Houseguest (1994)                   0.1             0               1.0
jac_own[38:40, 38:40]
                         Gaslight (1944) Gordy (1995) Great Escape, The (1963)
Gaslight (1944)                1.0000000            0                0.1007194
Gordy (1995)                   0.0000000          NaN                0.0000000
Great Escape, The (1963)       0.1007194            0                1.0000000
print(paste(sum(sample_sim_bin[,44]), "people have rated <Homage (1995)> 3 or higher."))
[1] "0 people have rated <Homage (1995)> 3 or higher."
print(paste(sum(sample_sim_bin[,39]), "people have rated <Gordy (1995)> 3 or higher."))
[1] "0 people have rated <Gordy (1995)> 3 or higher."

Bei Durchsuchung des Datensatzes ist auffallend, dass diese Filme nur nagative Bewertungen enthalten. Durch die Implementierung der Jaccard Similarity entsteht dadurch im Nenner eine 0, was zu einer jaccard similarity von NA führt.

Als Nächstes wird die normierte Cosine Ähnlichkeitsmatrix berechnet.

mean_total <- mean(sample_sim_wide_norm, na.rm=TRUE)

for(col_i in 1:dim(sample_sim_wide_norm)[2])
{
  # replace nas with 0 (non adjusted cosine similarity)
  mean_col = mean(sample_sim_wide_norm[,col_i], na.rm=TRUE)
  #print(mean_col)
  sample_sim_wide_norm[is.na(sample_sim_wide_norm[,col_i]), col_i] <- mean_col

}

start.time <- Sys.time()
cosine_sim_norm <- cosine_sim2(t(sample_sim_wide_norm), t(sample_sim_wide_norm))
end.time <- Sys.time()
elapsed.time <- round((end.time - start.time), 3)
print(elapsed.time)
Time difference of 0.046 secs
plot_sim(cosine_sim_norm)

In dieser Darstellung ist die normierte cosine similarity dargestellt. Für die Normierung wurde min-max Normailisierung gewählt, mit dem Mittelwert der ratings pro Film als NA Ersatz. Dadurch entsteht wie erwartet grundsätzlich eine höhere similarity, wessen Werte sich zwischen 0 und 1 ansiedeln.

p1 <- plot_sim(cosine_sim_matrix)
p2 <- plot_sim(jac_own)
p3 <- plot_sim(cosine_sim_norm)

grid.arrange(p1, p2, p3, ncol = 3, nrow = 1)

Die unnormalisierten Cosine und Jaccard Ähnlichkeitsmatrizen sind sich sehr ähnlich. Sie weisen ähnliche strukturelle Eigenschaften auf. Die Jaccard Ähnlichkeitsmatrix enthält generell etwas tiefere Werte und ist deshalb heller. Es werden jedoch einzelne Punkte sichbar, welche eine Ähnlichkeit von 1 aufweisen.

print(jac_own[25:28, 25:27])
                               Dadetown (1995) Damsel in Distress, A (1937) Designated Mourner, The (1997)
Dadetown (1995)                              1                            0                              1
Damsel in Distress, A (1937)                 0                            1                              0
Designated Mourner, The (1997)               1                            0                              1
Doom Generation, The (1995)                  0                            0                              0
print(sample_sim_wide[,'Designated Mourner, The (1997)'] %>% drop_na())
print(sample_sim_wide[,'Dadetown (1995)'] %>% drop_na())

TODO: klarere darstellung evtl?

Dies ist beispielsweise bei den Filmen ‘Designated Mourner, The (1997)’ und ‘Dadetown (1995)’ der Fall. Diese Filme wurde drei, bzw. ein Mal bewertet. Der Rest der Werte ist jeweils auf 0 gesetzt. Deshalb wird die Cosine Ähnlichkeit zwischen diesen Werten kaum eine Aussage treffen können. Diese Werte sind deshalb von niedriger Bedeutung.

Die normalisierte Cosine Ähnlichkeitsmatrix ist etwas anders in der Struktur. Dadurch, dass die Mittelwerte der jeweiligen Filmbewertungen durch die fehlenden Daten ein hohes Gewicht auf die Daten haben, entstehen generell grössere Abstände zwischen den Bewertungen einzelner Filme. Diese werden sichtbar durch Streifen. Dadurch liegt ein stärkerer Fokus auf den Unterschieden der Filmbewertungen im Allgemeinen und weniger auf den Unterschieden einzelner Ratings. Dadurch verschwinden die similarities einzelner Filme ein wenig und die Grafik ist schwerer zu lesen. Wäre die Matrix weniger sparce, würde diese Impuation nicht so stark ins Gewicht fallen und die Darstellung könnte besser abgelesen werden. In diesem Falle ist diese Grafik jedoch nicht gut geeignet.


Implementierung Top-N Metriken

Catalog coverage and System-level novelty

rec <- Recommender(train, method = "IBCF", param=list(method="Cosine", k=30, normalize = NULL, na_as_zero = TRUE)) #normalize = 'center', 'Z-score'

df_coverage <- show_coverage(c(5,10,15,20,25,30), rec)
df_novelty <- show_novelty(c(5,10,15,20,25,30))

df_combined <- inner_join(df_coverage, df_novelty, by = 'N')

Coverage: Summe aller unterschiedlichen Produkte, welche in den Top-N Listen aller KundInnen insgesamt auftauchen dividiert durch die Menge aller Produkte. Novelty: Mittel der Shannon Information der Popularität der Produkte in der Top-N Liste gemittelt über alle KundInnen.

ggplot(data=df_combined, aes(x=coverage, y=novelty, group=1)) +
  geom_line() +
  geom_text(aes(label=N), vjust=-.25, hjust=-.05, show.legend = FALSE) +
  labs(
    title = "Coverage gegenüber Novelty für verschiedene N",
    y = "Novelty",
    x = "Coverage"
  ) +
  theme(text = element_text(size = 12))

TODO: das ganze im selben plot für verschiedene reduktionen darstellen + text + verschiedene Datenreduktionen


Implementierung Top-N Monitor

Fixiere 20 zufällig gewählte Testkunden für alle Modellvergleiche

Bestimme den Anteil der Top-N Empfehlung nach Genres pro Kunde

TODO: Hier auch 3 mal? - nein TODO: IBCF im titel erwähnen

rec <- Recommender(train, method = "IBCF", param=list(method="Cosine", k=30, normalize = NULL, na_as_zero = TRUE))
df_user_genres_top_n <- create_df_user_genres_top_n(rec, genres)
show_genre_fraction_plot(df_user_genres_top_n, df_user_genres_top_n$count_top_n, "Anteil Genres in Top-N Empfehlung von 20 zuf. Kunden")

TODO: text

Auf diesem Plot ist die Unterschiedliche Verteilung der Genres in den Top-N Empfehlungen für die verschiedenen Kunden zu sehen. Es fällt auf, dass bei diesem Recommender durchaus verschiedenartige Verteilungen bei den Genres für die verschiednen Nutzer auftreten.

Bestimme pro Kunde den Anteil nach Genres seiner Top-Filme (=Filme, welche vom Kunden die besten Bewertungen erhalten haben)

df_user_genres_best <- create_df_user_genres_best(movies, df_user_genres_top_n, genres)
show_genre_fraction_plot(df_user_genres_best, df_user_genres_best$count_best, "Anteil Genres der bestbewerteten Filme von 20 zuf. Kunden")

Auf diesem Plot ist die Unterschiedliche Verteilung der Genres bei den bestbewerteten Filmen für die verschiedenen Kunden zu sehen. Bestbewertet bedeutet in diesem Fall, dass die Bewertung eines Filmes mindestens 0.5 höher sein muss, als die Durchschnittliche Bewertung des Nutzers. Es fällt auf, dass bei den Top-N Empfehlungen allgemein Action zu wenig empfohlen wurde. Comedy hingegen wurde häufig zu viel empfohlen. Bei genauerem betrachten fällt auf, dass dieser Recommeder beispielsweise bei Kunde Nr. 38 auf die Genres bezogen sehr schlechte Empfehlungen macht.

Vergleiche pro Kunde Top-Empfehlungen und Top-Filmen nach Genres

df_user_genres_best <- create_df_user_genres_best(movies, df_user_genres_top_n, genres)

rec <- Recommender(train, method = "IBCF", param=list(method="Cosine", k=30, normalize = NULL, na_as_zero = TRUE))
df_user_genres_top_n <- create_df_user_genres_top_n(rec, genres)
df_user_genres <- create_df_user_genres(df_user_genres_top_n, df_user_genres_best)
show_cleveland_dot_plot(df_user_genres, 'IBCF Recommender mit Cosine Similarity')

Auf diesem Plot ist ersichtlich welche Genres der IBCF Recommender mit Cosine Similarity für die 20 Kunden eher zu wenig oder zu viel empfiehlt. Beispielsweise Comedy macht bei den bestbewerteten Filmen im Durchschnitt ungefähr 12% aus, erscheint in den Top-N Empfehlungen jedoch zu etwa 21%.

rec <- Recommender(train, method = "UBCF", param=list(method="Jaccard", normalize = NULL))
df_user_genres_top_n <- create_df_user_genres_top_n(rec, genres)
df_user_genres <- create_df_user_genres(df_user_genres_top_n, df_user_genres_best)
show_cleveland_dot_plot(df_user_genres, 'UBCF Recommender mit Jaccard Similarity')

rec <- Recommender(train, method = "POPULAR")
df_user_genres_top_n <- create_df_user_genres_top_n(rec, genres)
df_user_genres <- create_df_user_genres(df_user_genres_top_n, df_user_genres_best)
show_cleveland_dot_plot(df_user_genres, 'Popular Recommender')

TODO: add plot for svd recommender

Definiere eine Qualitätsmetrik für Top-N Listen und teste sie


algorithms <- list(
  "IBCF cosine" = list(name="IBCF", param=list(k = 30, method = "cosine", normalize = NULL, na_as_zero = TRUE), desc = 'IBCF Recommender mit Cosine Similarity'),
  "UBCF Jaccard" = list(name="UBCF", param=list(method = "jaccard"), desc = 'UBCF Recommender mit Jaccard Similarity'),
  "Popular" = list(name="POPULAR", param=NULL, desc = 'Popular Recommender')
)

errors <- vector()
algos <- vector()
for (algo in algorithms) {
  rec <- Recommender(train, method = algo$name, param=algo$param)
  df_user_genres_top_n <- create_df_user_genres_top_n(rec, genres)
  df_user_genres <- create_df_user_genres(df_user_genres_top_n, df_user_genres_best)
  error <- compute_mean_absolute_percentage_error(df_user_genres)
  algos <- c(algos, algo$desc)
  errors <- c(errors, error)
}

df_error <- data.frame(description = algos, error = errors)


ggplot(df_error, aes(x=description, y = error)) + 
  geom_col(fill = 'steelblue') +
  coord_flip() +
  scale_y_continuous(expand = c(0,0)) +
  geom_text(aes(label=error), hjust=1.5, color = 'white') +
  labs(
    title = "Mittlerer absoluter prozentualer Fehler der \nGenre-Anteile in den Top-N Empfehlungen",
    x = element_blank(), 
    y = "Mittlerer absoluter prozentualer Fehler",
    fill = element_blank()
  ) +
  theme_classic() + 
  theme(
    text = element_text(size = 12),
    legend.position = 'bottom'
  )

abs(df1_drama - df2_drama) + abs(df1_actions - df2_action) + …

LS0tCnRpdGxlOiAiQ29sbGFib3JhdGl2ZSBNb3ZpZSBSZWNvbW1lbmRlciIKYXV0aG9yOiAiUGFzY2FsIEJlcmdlciwgTGVhIELDvHRsZXIgJiBKb8OrbCBHcm9zamVhbiIKb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6IGRlZmF1bHQKICBwZGZfZG9jdW1lbnQ6IGRlZmF1bHQKLS0tClItVmVyc2lvbjogKipbRGVmYXVsdF0gWzMyLWJpdF0gQzpcXFByb2dyYW0gRmlsZXNcXFJcXFItNC4xLjAqKgoKSW4gZm9sZ2VuZGVtIE5vdGVib29rIHdlcmRlbiBhbmhhbmQgZGVzICdNb3ZpZWxlbnMnIERhdGVuc2F0emVzIGF1cyBkZW0gUGFrZXQgUmVjb21tZW5kZXJMYWIgdmVyc2NoaWVkZW5lIFJlY29tbWVuZGVyIGVyc3RlbGx0LiBFcyB3ZXJkZW4gdmVyc2NoaWVkZW5lIFJlY29tbWVuZGVyIHVuZCB2ZXJzY2hpZWRlbmUgw4RobmxpY2hrZWl0ZW4gdmVyd2VuZGV0LCB1bSBkaWVzZSB6dSB2ZXJnbGVpY2hlbiB1bmQgYXVzenV3ZXJ0ZW4uIFppZWwgaXN0IGVzLCBlaW4gbcO2Z2xpY2hzdCBndXRlciBSZWNvbW1lbmRlciB6dSBlcnN0ZWxsZW4gdW5kIHp1IHZlcnN0ZWhlbiB3aWUgZGllc2VyIGZ1bmt0aW9uaWVydC4gWnVkZW0gc29sbCB2ZXJzdGFuZGVuIHdlcmRlbiB3aWUgZGllc2VyIGJld2VydGV0IHdpcmQgdW5kIHdhcyBpbiBkaWVzZW0gRmFsbGUgZWluICdndXRlcicgUmVjb21tZW5kZXIgYmVkZXV0ZXQuCgpEaWVzZXMgTm90ZWJvb2sga29uemVudHJpZXJ0IHNpY2ggYXVmIEVya2VubnRuaXNzZSB2b24gQXVzd2VydHVuZ2VuIHVuZCBWZXJnbGVpY2hlbi4gVW0gZWluZSBCZXNzZXJlIMOcYmVyc2ljaHQgenUgZXJoYWx0ZW4gd3VyZGVuIGdyb3NzZSBzaWNoIHdpZGVyaG9sZW5kZSBDb2RlcyBpbiBlaW5lbSAnaGVscGVyLlInIGZpbGUgYXVzZ2VsYWdlcnQuCgpgYGB7ciBlY2hvPUZBTFNFLCBjYWNoZT1GQUxTRSwgcmVzdWx0cz1GQUxTRSwgY29tbWVudD1GQUxTRSwgd2FybmluZz1GQUxTRX0KIyBuw7Z0aWdlIFBhY2tldGUKcGFja2FnZXMgPC0gYygidGlkeXZlcnNlIiwgImRhdGEudGFibGUiLCAibHVicmlkYXRlIiwgImdncGxvdDIiLCAiZ2d0aGVtZXMiLCAicmVjb21tZW5kZXJsYWIiLCAia25pdHIiLCAncGFscycsICdSQ29sb3JCcmV3ZXInLCAnbGF0dGljZScsICdncmlkJywgJ2dyaWRFeHRyYScpCgojIE5vY2ggbmljaHQgaW5zdGFsbGllcnRlIFBha2V0ZSBpbnN0YWxsaWVyZW4KaW5zdGFsbGVkX3BhY2thZ2VzIDwtIHBhY2thZ2VzICVpbiUgcm93bmFtZXMoaW5zdGFsbGVkLnBhY2thZ2VzKCkpCgppZiAoYW55KGluc3RhbGxlZF9wYWNrYWdlcyA9PSBGQUxTRSkpIHsKICBpbnN0YWxsLnBhY2thZ2VzKHBhY2thZ2VzWyFpbnN0YWxsZWRfcGFja2FnZXNdKQp9CgojIExhZGVuIGRlciBQYWNrZXRlCmludmlzaWJsZShsYXBwbHkocGFja2FnZXMsIGxpYnJhcnksIGNoYXJhY3Rlci5vbmx5ID0gVFJVRSkpCgojIEltcG9ydGllcmVuIHZvbiBGdW5rdGlvbmVuZSBhdXMgaGVscGVyIGZpbGUKc291cmNlKCJoZWxwZXIuUiIpCgojIGNoYW5nZSBvcHRpb25zCm9wdGlvbnMoZHBseXIuc3VtbWFyaXNlLmluZm9ybSA9IEZBTFNFKQpgYGAKCioqKgojIyMjIGRhdGEgd3JhbmdsaW5nCmBgYHtyfQojIERhdGVuIGltcG9ydGllcmVuCmRhdGEoTW92aWVMZW5zZSkKCiMgZGF0YWZyYW1lIGVyc3RlbGxlbgptb3ZpZXMgPC0gYXMoTW92aWVMZW5zZSwgImRhdGEuZnJhbWUiKQptb3ZpZXMgPC0gbW92aWVzICU+JSBtdXRhdGVfaWYoaXMuY2hhcmFjdGVyLCBhcy5mYWN0b3IpCgojIGJyZWl0ZSB2ZXJzaW9uIGRlcyBkYXRhZnJhbWUgZXJzdGVsbGVuCm1vdmllc193aWRlciA8LSBwaXZvdF93aWRlcigKICBtb3ZpZXMsCiAgaWRfY29scyA9IHVzZXIsCiAgbmFtZXNfZnJvbSA9IGl0ZW0sCiAgdmFsdWVzX2Zyb20gPSByYXRpbmcsCiAgdmFsdWVzX2ZpbGwgPSBOVUxMLAopCmBgYAoKKioqCiMjIEV4cGxvcmF0aXZlIERhdGVuYW5hbHlzZQpgYGB7cn0KZGZfMSA8LSBtb3ZpZXMgJT4lIGdyb3VwX2J5KGl0ZW0pICU+JSAgc3VtbWFyaXplKG1lYW5fcmF0aW5nID0gbWVhbihyYXRpbmcpKSAlPiUgc2FtcGxlX24oMTUpICU+JSBhcnJhbmdlKGRlc2MobWVhbl9yYXRpbmcpKQoKZ2dwbG90KGRmXzEsIGFlcyh5ID0gcmVvcmRlcihpdGVtLCArbWVhbl9yYXRpbmcpLCB4ID0gbWVhbl9yYXRpbmcpKSArCiAgZ2VvbV9jb2woYWxwaGEgPSAxLCBmaWxsID0gJ3N0ZWVsYmx1ZScpICsKICBzY2FsZV95X2Rpc2NyZXRlKGV4cGFuZCA9IGMoMCwwKSkgKwogIHNjYWxlX3hfY29udGludW91cyhleHBhbmQgPSBjKDAsMCkpICsKICBnZW9tX3RleHQoYWVzKGxhYmVsPXJvdW5kKG1lYW5fcmF0aW5nLDIpKSwgaGp1c3QgPSAxLjMsIGNvbG9yID0gJ3doaXRlJykgKwogIGxhYnMoCiAgICB0aXRsZSA9ICJEdXJjaHNjaG5pdHRsaWNoZSBGaWxtYmV3ZXJ0dW5nIiwKICAgIHN1YnRpdGxlID0gIlp1ZsOkbGxpZ2UgU3RpY2hwcm9iZSB2b24gMTUgRmlsbWVuIiwKICAgIHkgPSBlbGVtZW50X2JsYW5rKCksICAgIHggPSAiRGlyY2hzY2huaXR0bGljaCBCZXdlcnR1bmcgaW4gU3Rlcm5lbiIKICApICsKICB0aGVtZV9jbGFzc2ljKCkgKwogIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF9ibGFuaygpLAogICAgICAgIGF4aXMudGlja3MueCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICBheGlzLmxpbmUueCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMikgIyB0ZXh0IHNpemUKICApCgpgYGAKVW0gZWluZW4gZXJzdGVuIMOcYmVyYmxpY2sgw7xiZXIgZGllIERhdGVuIHp1IGVyaGFsdGVuIHd1cmRlIGhpZXIgZWluIFBsb3Qgdm9uIDE1IHp1ZsOkbGxpZyBnZXfDpGhsdGVuIEZpbG1lbiBzYW10IGRlciBEdXJjaHNjaG5pdHRzYmV3ZXJ0dW5nIGdlcGxvdHRldC4KCgoqKioKIyMjIyAxLiBXZWxjaGVzIHNpbmQgZGllIGFtIGjDpHVmaWdzdGVuIGdlc2NoYXV0ZW4gR2VucmVzIC8gRmlsbWU/CmBgYHtyfQptb3ZpZXNfZ2VucmUgPC0gTW92aWVMZW5zZU1ldGEgJT4lCiAgcmVuYW1lKGl0ZW0gPSB0aXRsZSkKbW92aWVzX2dlbnJlJHVybCA8LSBOVUxMCm1vdmllc19nZW5yZVttb3ZpZXNfZ2VucmUgPT0gMF0gPC0gTkEKYSA8LSB3aGljaChtb3ZpZXNfZ2VucmU9PTEsYXJyLmluZD1UUlVFKQptb3ZpZXNfZ2VucmVbYV0gPC0gbmFtZXMobW92aWVzX2dlbnJlKVthWywiY29sIl1dCm1vdmllc19nZW5yZSA8LSBtb3ZpZXNfZ2VucmUgJT4lCiAgdW5pdGUoImdlbnJlcyIsIHVua25vd246V2VzdGVybiwgc2VwPSAiLCIsIAogICAgICAgIHJlbW92ZSA9IFRSVUUsIG5hLnJtID0gVFJVRSkKZ2VucmVzPC1tZXJnZSh4PW1vdmllcyx5PW1vdmllc19nZW5yZSxieT0iaXRlbSIsYWxsLng9VFJVRSklPiUKICBtdXRhdGUoZ2VucmVzID0gc3Ryc3BsaXQoYXMuY2hhcmFjdGVyKGdlbnJlcyksICIsIikpICU+JQogIHVubmVzdChnZW5yZXMpCgpkZjFhIDwtIG1vdmllcyU+JQogIGdyb3VwX2J5KGl0ZW0pJT4lCiAgc3VtbWFyaXplKGNvdW50PW4oKSklPiUKICB1bmdyb3VwKCklPiUKICBhcnJhbmdlKGRlc2MoY291bnQpKQoKZGYxYSA8LSBoZWFkKGRmMWEsIDEwKQoKZGYxYSAlPiUKICBtdXRhdGUoaXRlbSA9IGZjdF9yZW9yZGVyKGl0ZW0sIGNvdW50KSklPiUKICBnZ3Bsb3QoYWVzKHggPSBjb3VudCwgeSA9IGl0ZW0pKSsKICBnZW9tX2NvbChhbHBoYSA9IDEsIGZpbGwgPSAnc3RlZWxibHVlJykrCiAgc2NhbGVfeV9kaXNjcmV0ZShleHBhbmQgPSBjKDAsMCkpICsKICBzY2FsZV94X2NvbnRpbnVvdXMoZXhwYW5kID0gYygwLDApKSArCiAgZ2VvbV90ZXh0KGFlcyhsYWJlbD1yb3VuZChjb3VudCwyKSksIGhqdXN0ID0gMS4zLCBjb2xvciA9ICd3aGl0ZScpICsKICBsYWJzKAogICAgdGl0bGUgPSAiTWVpc3QgYmV3ZXJ0ZXRlIEZpbG1lIiwKICAgIHkgPSBlbGVtZW50X2JsYW5rKCksICAgIHggPSAiQW56YWhsIEJld2VydHVuZ2VuIgogICkgKwogIHRoZW1lX2NsYXNzaWMoKSArCiAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X2JsYW5rKCksCiAgICAgICAgYXhpcy50aWNrcy54ID0gZWxlbWVudF9ibGFuaygpLAogICAgICAgIGF4aXMubGluZS54ID0gZWxlbWVudF9ibGFuaygpLAogICAgICAgIHRleHQgPSBlbGVtZW50X3RleHQoc2l6ZSA9IDEyKSAjIHRleHQgc2l6ZQogICkKYGBgCkRhIGluIHVuc2VyZW0gRGF0ZW5zYXR6IG51ciBkaWUgQW56YWhsIFJhdGluZ3Mgdm9uIEZpbG1lbiBnZWdlYmVuIGlzdCwgZ2VoZW4gd2lyIGRhdm9uIGF1cywgZGFzcyBkaWUgbWVpc3QgYmV3ZXJ0ZXRlbiwgYXVjaCBkaWUgYW0gbWVpc3QgZ2VzY2hhdXRlbiBGaWxtZSBzaW5kLiBJbiBkZXIgR3JhZmlrIHNpZWh0IG1hbiBkaWUgMTAgbWVpc3QgYmV3ZXJ0ZXRlbiBGaWxtZS4KCmBgYHtyfQpkZjFiIDwtIGdlbnJlcyU+JQogIGdyb3VwX2J5KGdlbnJlcyklPiUKICBzdW1tYXJpemUoY291bnQ9bigpKSU+JQogIHVuZ3JvdXAoKSU+JQogIGFycmFuZ2UoZGVzYyhjb3VudCkpCgpkZjFiJT4lCiAgbXV0YXRlKGdlbnJlcyA9IGZjdF9yZW9yZGVyKGdlbnJlcywgY291bnQpKSU+JQogIGdncGxvdChhZXMoeCA9IGNvdW50LCB5ID0gZ2VucmVzKSkrCiAgZ2VvbV9jb2woYWxwaGEgPSAxLCBmaWxsID0gJ3N0ZWVsYmx1ZScpKwogIGdlb21fdGV4dChhZXMobGFiZWw9cm91bmQoY291bnQsMikpLCBoanVzdCA9IC0wLjIsIGNvbG9yID0gJ2JsYWNrJykgKwogIHNjYWxlX3lfZGlzY3JldGUoZXhwYW5kID0gYygwLDApKSArCiAgc2NhbGVfeF9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSwgbGltaXRzID0gYygwLDQ1MDAwKSkgKwogIGdlb21fdGV4dChhZXMobGFiZWw9Y291bnQsMiksIGhqdXN0ID0gMS4zLCBjb2xvciA9ICd3aGl0ZScpICsKICBsYWJzKAogICAgdGl0bGUgPSAiTWVpc3QgYmV3ZXJ0ZXRlIEdlbnJlcyIsCiAgICB5ID0gZWxlbWVudF9ibGFuaygpLCAgICB4ID0gIkFuemFobCBCZXdlcnR1bmdlbiIKICApICsKICB0aGVtZV9jbGFzc2ljKCkgKwogIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF9ibGFuaygpLAogICAgICAgIGF4aXMudGlja3MueCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICBheGlzLmxpbmUueCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMikgIyB0ZXh0IHNpemUKICApCmBgYApBdWNoIGhpZXIgd2lyZCBkYXZvbiBhdXNnZWdhbmdlbiwgZGFzcyBkaWUgZW5yZXMsIHdlbGNoZSBhbSBow6R1Zmlnc3RlbiBiZXdlcnRldCB3dXJkZW4gYXVjaCBhbSBow6R1Zmlnc3QgZ2VzY2hhdXQgd3VyZGVuLiBJbiBkZXIgR3JhZmlrIGlzdCB6dSBzZWhlbiwgZGFzcyBEcmFtYSBkYXMgdG9wIEdlbnJlcyBpc3QsIGdlZm9sZ3Qgdm9uIENvbWVkeSB1bmQgQWN0aW9uLgoKKioqCiMjIyMgMi4gV2llIHZlcnRlaWxlbiBzaWNoIGRpZSBLdW5kZW5yYXRpbmdzIGdlc2FtdGhhZnQgdW5kIG5hY2ggR2VucmVzPwpgYGB7cn0KZ2dwbG90KG1vdmllcywgYWVzKHggPSByYXRpbmcpKSArCiAgZ2VvbV9iYXIoYWxwaGEgPSAxLCBmaWxsID0gJ3N0ZWVsYmx1ZScpICsKICBnZW9tX3RleHQoc3RhdD0nY291bnQnLCBhZXMobGFiZWw9Li5jb3VudC4uKSwgdmp1c3Q9MS41LCBjb2xvciA9ICd3aGl0ZScpICsKICBzY2FsZV95X2NvbnRpbnVvdXMoZXhwYW5kID0gYygwLDApKSArCiAgc2NhbGVfeF9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSkgKwogIGxhYnMoCiAgICB0aXRsZSA9ICJWZXJ0ZWlsdW5nIEt1bmRlbnJhdGluZ3MgZ2VzYW10aGFmdCIsCiAgICBzdWJ0aXRsZSA9IHBhc3RlKCJOID0gIiwgbnJvdyhtb3ZpZXMpLCAiIEJld2VydHVuZ2VuIiksCiAgICB4ID0gIkt1bmRlbmJld2VydHVuZ2VuIiwgCiAgICB5ID0gIkFuemFobCIsCiAgICBmaWxsID0gZWxlbWVudF9ibGFuaygpCiAgKSArCiAgdGhlbWVfY2xhc3NpYygpICsKICB0aGVtZSgKICAgIHRleHQgPSBlbGVtZW50X3RleHQoc2l6ZSA9IDEyKQogICkKYGBgCkluIGRpZXNlciBHcmFmaWsgaXN0IGRpZSBWZXJ0ZWlsdW5nIGRlciBiZXdlcnR1bmdlbiB6dSBzZWhlbi4gRGllIEJld2VydHVuZ2VuIDQgdW5kIDUgd2lyZGVuIGtsYXIgYW0gaMOkdWZpZ3N0ZW4gdmVyZ2ViZW4sIHdvYmVpIDEgdW5kIDIgZWhlciBzZWx0ZW4gYmV3ZXJ0ZXQgd2VyZGVuLgoKYGBge3Igd2FybmluZz1GQUxTRSwgZmlnLndpZHRoID0gMTUsIGZpZy5oZWlnaHQgPSAxMX0KIyBnZXQgcmF0aW5nIGNvdW50IHBlciB1c2VyLCBhZGQgYXMgY29sdW1uIGZvciBmdXJ0aGVyIHByb2Nlc3NpbmcKY291bnRzIDwtIG1vdmllcyAlPiUgZ3JvdXBfYnkodXNlcikgJT4lIGNvdW50KCkKbW92aWVzMiA8LSBtZXJnZShtb3ZpZXMsIGNvdW50cywgYnk9InVzZXIiKQptb3ZpZXNfd2lkZXIyIDwtIG1lcmdlKG1vdmllc193aWRlciwgY291bnRzLCBieT0idXNlciIpCgojIGF2b2lkIHVzZXJzIHdpdGggYWxtb3N0IG5vIHJhdGluZ3MsIHVzZSBtZWRpYW4gYXMgdGhyZXNob2xkCm1lZGlhbl9jb3VudCA8LSBtZWRpYW4oY291bnRzJG4pCgojIGdldCBzYW1wbGUKc2V0LnNlZWQoNjIzKQptb3ZpZXNfc2FtcGxlIDwtIG1vdmllc193aWRlcjIgJT4lIGZpbHRlcihuID4gbWVkaWFuX2NvdW50KSAlPiUgc2FtcGxlX24oNSkKCiMgY3JlYXRlIGxvbmcgdGFibGUKbW92aWVzX3NhbXBsZV9sb25nIDwtIGZpbHRlcihtb3ZpZXMyLCB1c2VyICVpbiUgbW92aWVzX3NhbXBsZSR1c2VyKQoKIyBkcm9wIGl0ZW0gbmFtZXMsIAptb3ZpZXNfc2FtcGxlX2xvbmcgPC0gc3Vic2V0KG1vdmllc19zYW1wbGVfbG9uZywgc2VsZWN0ID0gLWMoaXRlbSkpCgpkZjJiIDwtIGdlbnJlcyU+JQogIGdyb3VwX2J5KGdlbnJlcykKICAKbW92aWVzX3NhbXBsZV9sb25nX2dyb3VwZWQgPC0gbW92aWVzX3NhbXBsZV9sb25nICU+JSBncm91cF9ieSh1c2VyLCByYXRpbmcpICU+JSBzdW1tYXJpc2UocmF0aW5nX2RlbnMgPSBsZW5ndGgodXNlcikgLyBmaXJzdChuKSwgdXNlciA9IGZpcnN0KHVzZXIpLCBuPWZpcnN0KG4pLCByYXRpbmcgPSBmaXJzdChyYXRpbmcpKQogIApnZ3Bsb3QoZ2VucmVzLCBhZXMoeCA9IHJhdGluZywgZmlsbCA9IGdlbnJlcykpICsKICBnZW9tX2JhcihhbHBoYSA9IDEsIGJpbnMgPSAxMCkgKwogIGZhY2V0X3dyYXAofmdlbnJlcykrCiAgc2NhbGVfeV9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSkgKwogIHNjYWxlX3hfY29udGludW91cyhleHBhbmQgPSBjKDAsMCkpICsKICBsYWJzKAogICAgdGl0bGUgPSAiVmVydGVpbHVuZyBLdW5kZW5yYXRpbmdzIG5hY2ggR2VucmVzIiwKICAgIHN1YnRpdGxlID0gcGFzdGUoIk4gPSAiLCBucm93KG1vdmllcyksICIgQmV3ZXJ0dW5nZW4iKSwKICAgIHggPSAiRHVyY2hzY2huaXR0bGljaGUgQmV3ZXJ0dW5nIiwgCiAgICB5ID0gIkFuemFobCIsCiAgICBmaWxsID0gZWxlbWVudF9ibGFuaygpCiAgKSArCiAgdGhlbWUoCiAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMiksCiAgICBsZWdlbmQucG9zaXRpb24gPSAnbm9uZScKICApCmBgYApIaWVyIGlzdCB6dSBzZWhlbiwgZGFzcyBkYXMgR2VucmVzIERyYW1hIGFtIG1laXN0ZW4gYmV3ZXJ0ZXQgd3VyZGUsIHdvYmVpIERva3VtZW50YXRpb25lbiBhbSB3ZW5pZ3N0ZW4gQmV3ZXJ0dW5nZW4gZXJoYWx0ZW4gaGFiZW4uIERpZSBCZXdlcnR1bmdlbiBwcm8gR2VucmVzIHZlcnRlaWxlbiBzaWNoIGpld2VpbHMgc2VociDDpGhubGljaC4gRGllIFZlcnRlaWx1bmdlbiBkZXIgZWluemVsbmVuIEdlbnJlcyBzaW5kIGViZW5mYWxscyDDpGhubGljaCB2ZXJ0ZWlsdCB3aWUgZGllIGJld2VydHVuZ2VuIGdlc2FtdGhhZnQuCgoqKioKIyMjIyAzLldpZSB2ZXJ0ZWlsZW4gc2ljaCBkaWUgbWl0dGxlcmVuIEt1bmRlbnJhdGluZ3MgcHJvIEZpbG0/CmBgYHtyfQpkZjMgPC0gbW92aWVzICU+JSAKICBncm91cF9ieShpdGVtKSAlPiUgIAogIHN1bW1hcml6ZSgKICAgIG1lYW5fcmF0aW5nID0gbWVhbihyYXRpbmcpLAogICAgcmF0aW5ncyA9IG4oKQogICkgJT4lIAogIG11dGF0ZSgKICAgIG1vcmVfdGhhbl81MCA9IGlmZWxzZShyYXRpbmdzID49IDUwLCAnYikgbWVociBhbHMgNTAgQmV3ZXJ0dW5nZW4nLCAnYSkgd2VuaWdlciBhbHMgNTAgQmV3ZXJ0dWdlbicpCiAgKQoKZ2dwbG90KGRmMywgYWVzKHggPSBtZWFuX3JhdGluZykpICsKICBnZW9tX2hpc3RvZ3JhbShhbHBoYSA9IDEsIGZpbGwgPSAnc3RlZWxibHVlJywgYmlud2lkdGggPSAwLjA2KSArCiAgc2NhbGVfeV9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSkgKwogIHNjYWxlX3hfY29udGludW91cyhleHBhbmQgPSBjKDAsMCkpICsKICBsYWJzKAogICAgdGl0bGUgPSAiVmVydGVpbHVuZyBtaXR0bGVyZSBLdW5kZW5yYXRpbmdzIHBybyBGaWxtIiwKICAgIHN1YnRpdGxlID0gcGFzdGUoIk4gPSAiLCBucm93KG1vdmllcyksICIgQmV3ZXJ0dW5nZW4iKSwKICAgIHggPSAiRHVyY2hzY2huaXR0bGljaGUgQmV3ZXJ0dW5nIiwgCiAgICB5ID0gIkRpY2h0ZSIKICApICsKICB0aGVtZV9jbGFzc2ljKCkgKwogIHRoZW1lKHRleHQgPSBlbGVtZW50X3RleHQoc2l6ZSA9IDEyKQogICkKYGBgCkluIGRpZXNlciBHcmFmaWsgaXN0IGRpZSBkdXJjaHNjaG5pdHRsaWNoZSBCZXdlcnR1bmcgcHJvIEZpbG0genUgc2VoZW4sIHdvYmVpIGF1Y2ggaGllciB6dSBzZWhlbiBpc3QgLGRhc3MgZGllIGRpZSBtZWlzdGVuIEZpbG1lIGVpbmUgRHVyY2hzY2huaXR0bGljaGUgQmV3ZXJ0dW5nIHZvbiBjYS4gMyAtIDMuNSBoYWJlbi4KQXVmZsOkbGxpZyBpc3QsIGRhc3MgYmVpIGRlbiBkaXN0aW5rdGVuIFdlcnRlbiAoMSwgMiwgMywgNCwgJiA1KSBhdXNzcmVpc3NlciB6dSBlcmtlbm5lbiBzaW5kLiBEaWVzIGxpZWd0IGFuIEZpbG1lbix3ZWxjaGUgbnVyIHdlbmlnZSBtYWxlIG9kZXIgbnVyIGVpbm1hbCBiZXdlcnRldCB3dXJkZW4uCgpgYGB7cn0KZ2dwbG90KGRmMywgYWVzKHggPSBtZWFuX3JhdGluZywgZmlsbCA9IG1vcmVfdGhhbl81MCkpICsKICBnZW9tX2RlbnNpdHkoYWxwaGEgPSAwLjUsIGJ3ID0gMC4wOCkgKwogIHNjYWxlX3lfY29udGludW91cyhleHBhbmQgPSBjKDAsMCkpICsKICBzY2FsZV94X2NvbnRpbnVvdXMoZXhwYW5kID0gYygwLDApKSArCiAgbGFicygKICAgIHRpdGxlID0gIlZlcnRlaWx1bmcgbWl0dGxlcmUgS3VuZGVucmF0aW5ncyBwcm8gRmlsbSIsCiAgICBzdWJ0aXRsZSA9ICJOID0gMTY2NCBGaWxtZSIsCiAgICB4ID0gIkR1cmNoc2Nobml0dGxpY2hlIEJld2VydHVuZyIsIAogICAgeSA9ICJEaWNodGUiLAogICAgZmlsbCA9IGVsZW1lbnRfYmxhbmsoKQogICkgKwogIHRoZW1lX2NsYXNzaWMoKSArCiAgdGhlbWUoCiAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMiksCiAgICBsZWdlbmQucG9zaXRpb24gPSAnYm90dG9tJwogICkKYGBgClRPRE86IE4gPSBBbnphaGwgYmV3ZXJ0dW5nZW4gZsO8ciBLYXRlZ29yaWUgYSAmIGIKCkbDvHIgZGllc2UgR3JhZmlrIHd1cmRlbiBkaWUgRmlsbWUgaW4gendlaSBncnVwcGVuIHVudGVydGVpbHQ6IEZpbG1lIGRpZSB3ZW5pZ2VyIGFscyA1MCBiZXdlcnR1bmdlbiBlcmhhbHRlbiBoYWJlbiwgdW5kIEZpbG1lIHdlbGNoZSBtZWhyIGFscyA1MCBCZXdlcnR1bmdlbiBlcmhhbHRlbiBoYWJlbi4gSW4gZGVyIEdyYWZpayBpc3QgaW1lcm5vY2ggZGllIGR1cmNoc2Nobml0dGxpY2hlIEJld2VydHVuZyBkaWVzZXIgRmlsbWUgenUgc2VoZW4gd29iZWkgZGV1dGxpY2ggZXJrYW5udCB3ZXJkZW4ga2FubiwgZGFzcyBmaWxtZSB3ZWxjaGUgd2VuaWdlciBiZXdlcnR1bmdlbiBlcmhhbHRlbiBoYWJlbiwgdGVuZGVuemllbGwgYXVjaCBzY2hsZWNodGVyIGJld2VydGV0IHd1cmRlbi4KCioqKgojIyMjIDQuV2llIHN0YXJrIHN0cmV1ZW4gZGllIFJhdGluZ3Mgdm9uIGluZGl2aWR1ZWxsZW4gS3VuZGVuPwpgYGB7cn0KIyBOdW1iZXIgb2YgcmF0aW5ncyBwZXIgdXNlciBwZXIgcmF0aW5nIHZhbHVlCm1vdmllc19zYW1wbGVfbG9uZ19ncm91cGVkIDwtIG1vdmllc19zYW1wbGVfbG9uZyAlPiUgZ3JvdXBfYnkodXNlciwgcmF0aW5nKSAlPiUgc3VtbWFyaXNlKHJhdGluZ19kZW5zID0gbGVuZ3RoKHVzZXIpIC8gZmlyc3QobiksIHVzZXIgPSBmaXJzdCh1c2VyKSwgbj1maXJzdChuKSwgcmF0aW5nID0gZmlyc3QocmF0aW5nKSkKCm1vdmllc19zcGFuIDwtIG1vdmllcyAlPiUgZ3JvdXBfYnkodXNlcikgJT4lIAogIHN1bW1hcml6ZShtZWFuID0gbWVhbihyYXRpbmcpLCBtaW4gPSBtaW4ocmF0aW5nKSwgbWF4ID0gbWF4KHJhdGluZyksIHNwYW4gPSAobWF4KHJhdGluZykgLSBtaW4ocmF0aW5nKSkpCgpzZXQuc2VlZCgxMjMpCgpnZ3Bsb3QobW92aWVzX3NwYW4gICU+JSBncm91cF9ieShzcGFuKSAlPiUgc3VtbWFyaXNlKGNvdW50ID0gbigpKSwgYWVzKHg9c3BhbiwgeT1jb3VudCkpICsKICBnZW9tX2NvbChmaWxsID0gJ3N0ZWVsYmx1ZScpICsKICBzY2FsZV95X2NvbnRpbnVvdXMobGltaXRzID0gYygwLDgwMCksIGV4cGFuZCA9IGMoMCwwKSkgKwogIGdlb21fdGV4dChhZXMobGFiZWw9cm91bmQoY291bnQsMikpLCB2anVzdCA9IC0wLjcsIGNvbG9yID0gJ2JsYWNrJykgKwogIGxhYnMoCiAgICB0aXRsZSA9ICJTcGFubndlaXRlIEt1bmRlbnJhdGluZ3MiLAogICAgc3VidGl0bGUgPSAiIiwKICAgIHggPSAiU3Bhbm53ZWl0ZSIsIAogICAgeSA9ICJBbnphaGwgVXNlciIKICApKwogICAgdGhlbWVfY2xhc3NpYygpICsgCiAgdGhlbWUoCiAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMiksCiAgICBsZWdlbmQucG9zaXRpb24gPSAnYm90dG9tJwogICkKYGBgCkluIGRpZXNlbiBHcmFmaWtlbiBzZWhlbiB3aXIgZGV0YWlsbGllcnRlcmUgSW5mb3JtYXRpb25lbiDDvGJlciBkaWUgU3Bhbm53ZWl0ZSB1bmQgZGVuIE1pdHRlbHB1bmt0LiBJbiBkZXIgZXJzdGVuIMOcYmVyc2ljaHQgaXN0IGRpZSBTcGFubndlaXRlIHVuZCBkZXIgTWl0dGVscHVua3QgZWluemVsbmVyIEt1bmRlbiBkYXJnZXN0ZWxsdC4gRXMgZsOkbGx0IGF1ZiwgZGFzcyB0cm90eiBkZXMgdGVpbHdlaXNlIHJlbGF0aXYgaG9oZW0gTWl0dGVsd2VydCBhbGxlIFJhdGluZ3Mgdm9uIDEtNSBhYmdlZ2ViZW4gd3VyZGVuLiBFaW4gcmF0aW5nIHZvbiA1IHd1cmRlIHNvenVzYWdlbiBpbW1lciBhYmdlZ2ViZW4sIDEgbmljaHQgaW1tZXIuCkluIGRlciB6d2VpdGVuIMOcYmVyc2ljaHQgaXN0IGRpZSBTcGFubndlaXRlIGFsbGVyIEt1bmRlbiBkYXJnZXN0ZWxsdC4gSGllciB3aXJkIHNpY2h0YmFyLCBkYXNzIGRpZSBtZWlzdGVuIEt1bmRlbiBCZXdlcnR1bmdlbiB2b24gMS01IGFiZ2VnZWJlbiBoYWJlbiAoU3Bhbm53ZWl0ZT00KSwgdW5kIG51ciB3ZWluaWdlIHNlaHIgaG9tb2dlbiBiZXdlcnRldCBoYWJlbiAoU3Bhbm53ZWl0ZSA9IDEtMikuIEVpbmUga2xlaW5lIFNwYW5ud2VpdGUga2FubiBoaWVyIGF1Y2ggYXVmZ2V0cmV0ZW4gc2VpbiwgZGEgZGllc2UgVXNlciBzZWhyIHdlbmlnZSBCZXdlcnR1bmdlbiBhYmdlZ2ViZW4gaGFiZW4uCgoqKioKIyMjIyA1LldlbGNoZW4gRWluZmx1c3MgaGF0IGRpZSBOb3JtaWVydW5nIGRlciBSYXRpbmdzIHBybyBLdW5kZSBhdWYgZGVyZW4gVmVydGVpbHVuZz8KYGBge3J9Cm1vdmllc19zYW1wbGVfbG9uZ19ncm91cGVkIDwtIG1vdmllcyAlPiUgZ3JvdXBfYnkocmF0aW5nKSAlPiUgc3VtbWFyaXNlKHJhdGluZ19kZW5zID0gbigpKQoKZ2dwbG90KG1vdmllc19zYW1wbGVfbG9uZ19ncm91cGVkLCBhZXMoeD1yYXRpbmcsIHkgPSByYXRpbmdfZGVucykpICsgCiAgZ2VvbV9jb2woZmlsbCA9ICdzdGVlbGJsdWUnKSArCiAgc2NhbGVfeV9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSkgKwogIGdlb21fdGV4dChhZXMobGFiZWw9cm91bmQocmF0aW5nX2RlbnMsMikpLCB2anVzdCA9IDEuNSwgY29sb3IgPSAnd2hpdGUnKSArCiAgbGFicygKICAgIHRpdGxlID0gIkjDpHVmaWdrZWl0IGRlciBLdW5kZW5iZXdlcnR1bmdlbiIsCiAgICBzdWJ0aXRsZSA9IHBhc3RlKCJOID0iLCAgbnJvdyhtb3ZpZXMpLCAiIEJld2VydHVuZ2VuIiksCiAgICB4ID0gIlVzZXIgQmV3ZXJ0dW5nICgxLTUpIiwgCiAgICB5ID0gIkFuemFobCBCZXdlcnR1bmdlbiIsCiAgICBmaWxsID0gZWxlbWVudF9ibGFuaygpCiAgKSArCiAgc2NhbGVfZmlsbF9tYW51YWwoImxlZ2VuZCIsIHZhbHVlcyA9IGMoImN5YW4zIiwgImN5YW40IiwgImRhcmtvbGl2ZWdyZWVuMyIsICJkYXJrb2xpdmVncmVlbiIsICJjb3JhbDQiKQogICAgICAgICAgICAgICAgICAgICkrCiAgdGhlbWVfY2xhc3NpYygpICsgCiAgdGhlbWUoCiAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMiksCiAgICBsZWdlbmQucG9zaXRpb24gPSAnYm90dG9tJwogICkKYGBgCgpgYGB7cn0KTW92Tm9ybSA8LSBub3JtYWxpemUoTW92aWVMZW5zZSwgbWV0aG9kPSJaLXNjb3JlIikKbW92IDwtIGFzKE1vdk5vcm0sICJkYXRhLmZyYW1lIikKCmdncGxvdChtb3YsIGFlcyh4PXJhdGluZykpICsgCiAgZ2VvbV9oaXN0b2dyYW0oZmlsbCA9ICdzdGVlbGJsdWUnLCBiaW5zID0gNzApICsKICBzY2FsZV95X2NvbnRpbnVvdXMoZXhwYW5kID0gYygwLDApKSArCiAgc2NhbGVfeF9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSkgKwogIGxhYnMoCiAgICB0aXRsZSA9ICJIw6R1Zmlna2VpdCBkZXIgS3VuZGVuYmV3ZXJ0dW5nZW4iLAogICAgc3VidGl0bGUgPSBwYXN0ZSgiTiA9ICIsIG5yb3cobW92KSwgIkJld2VydHVuZ2VuIiksCiAgICB4ID0gIlVzZXIgQmV3ZXJ0dW5nIE5vcm1pZXJ0IiwgCiAgICB5ID0gIkFuemFobCBCZXdlcnR1bmdlbiIsCiAgICBmaWxsID0gZWxlbWVudF9ibGFuaygpCiAgKSArCiAgc2NhbGVfZmlsbF9tYW51YWwoImxlZ2VuZCIsIHZhbHVlcyA9IGMoImN5YW4zIiwgImN5YW40IiwgImRhcmtvbGl2ZWdyZWVuMyIsICJkYXJrb2xpdmVncmVlbiIsICJjb3JhbDQiKQogICAgICAgICAgICAgICAgICAgICkrCiAgdGhlbWVfY2xhc3NpYygpICsgCiAgdGhlbWUoCiAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMiksCiAgICBsZWdlbmQucG9zaXRpb24gPSAnYm90dG9tJwogICkKYGBgCgpEaWUgUmF0aW5ncyBzaW5kIG51biB1bmdlZsOkaHIgTm9ybWFsdmVydGVpbHQgbWl0IGVpbmVtIER1cmNoc2Nobml0dHNyYXRpbmcgdm9uIDAgdW5kIGVpbmVyIFN0YW5kYXJkYWJ3ZWljaHVuZyB2b24gMS4gCkVya2VubmJhciBpc3QsIGRhc3MgZGllIFZlcnRlaWx1bmcgcmVjaHRzc3RlaWwgdW5kIGxpbmtzc2NoaWVmIGlzdCwgYWxzbyBtZWhyaGVpdGxpY2ggcG9zaXRpdmUgQmV3ZXJ0dW5nZW4gYWJnZWdlYmVuIHd1cmRlbi4gCkR1cmNoIGRpZSBOb3JtaWVydW5nIGRlciBEYXRlbiB3ZXJkZW4gZGllIFJhdGluZ3MgamVkZXMgVXNlcnMgYXVmIGRpZXNlbGJlIFZlcnRlaWx1bmcgZ2VzdGF1Y2h0LCB3b2R1cmNoIG1hbiBkaWUgVmVydGVpbHVuZyBhbGxlciBEYXRlbiBhbmFseXNpZXJlbiBrYW5uLiBEYWR1cmNoIGhhdCBtYW4gYmVpc3BpZWxzd2Vpc2UgZGllIE3DtmdsaWNoa2VpdCBkaWUgZHVyY2hzY2huaXR0bGljaGUgQmV3ZXJ0dW5nc3RlbmRlbnogaGVyYXVzenVmaW5kZW4uIAoKKioqCiMjIyMgNi5XZWxjaGUgc3RydWt0dXJlbGxlbiBDaGFyYWt0ZXJpc3Rpa2EgKHouQi4gU3BhcnNpdHkpIHVuZCBBdWZmw6RsbGlna2VpdGVuIHplaWd0IGRpZSBVc2VyIEl0ZW0gTWF0cml4PwpgYGB7cn0KaW1hZ2UoYXMoTW92aWVMZW5zZSwgImRnQ01hdHJpeCIpKQpgYGAKSW4gZGllc2VyIEdyYWZpayB3ZXJkZW4gd2VyZGVuIGRpZSBCZXdlcnR1bmdlbiB2b24gVXNlcnMgKFJvdykgZGVuIEZpbG1lbiAoQ29sdW1uKSBnZWdlbsO8YmVyZ2VzdGVsbHQuIERpZSBBY2hzZW5iZXNjaHJpZnR1bmcga29ubnRlIG5pY2h0IGJlc3NlciBzcGVpemlmaXppZXJ0IHdlcmRlbi4KClVzZXJzIG1pdCB0aWVmZW4gSUQncyB1bmQgRmlsbWUgbWl0IGhvaGVuIElEJ3Mgd2Vpc2VuIHdlbmlnZXIgcmF0aW5ncyBhdWYuIEZpbG1lIG1pdCB0aWVmZXIgSUQgamVkb2NoIHNlaHIgdmllbGUuIERpZXMgZXJrbMOkcnQgZGllIG5pY2h0IHZvcmhhbmRlbmVuIERhdGVucHVua3RlIGluIGRlciBHcmFmaWsgb2JlbiByZWNodHMKQXVmZmFsbGVuZCBpc3QsIGRhc3MgZXMgZWluaWdlIHdlbmlnZSBVc2VyIGdpYnQsIGRpZSBmYXN0IGFsbGUgRmlsbWUgYmV3ZXJ0ZXQgaGFiZW4gKGVya2VubmJhciBkdXJjaCBkaWUgaG9yaXpvbnRhbGVuIHNjaGFyemVuIFN0cmljaGUpLiBEaWVzIHNjaGVpbmVuIHNlaHIgYWt0aXZlIEJld2VydGVyIHp1IHNlaW4uClZpZWxlIFVzZXJzIGhhYmVuIGplZG9jaCBudXIgZWluZW4ga2xlaW5lbiBUZWlsIGRlciBGaWxtZSBiZXdlcnRldC4KQmVpIGRlbiBGaWxtZW4gaXN0IGVpbmUgw6RobmxpY2hlIFRlbmRlbnogd2Focnp1bmVobWVuLCBqZWRvY2ggc2luZCBkaWUgdmVydGlrYWxlbiBTdHJpY2hlIGJyZWl0ZXIuIE3DtmdsaWNoZXJ3ZWlzZSBzaW5kIGRvcnQgZWluaWdlIGJlbGllYnRlIEZpbG1lIHp1c2FtbWVuZ2VmYXNzdC4KCmBgYHtyfQpzcGFyY2l0eSA8LSBzdW0oaXMubmEobW92aWVzX3dpZGVyWywtMV0pKSAvIHByb2QoZGltKG1vdmllc193aWRlcikpCnNwYXJjaXR5CmBgYApUT0RPOiBudXIgNi40JSBkZXIgRGF0ZW4gaGFiZW4gVmFsdWVzIC8gc2luZCBub24gTkEncy0gZWluIFVzZXIgaGF0IGltIGR1cmNoc2Nobml0dCA2LjQlIGRlciBGaWxtZSBiZXdlcnRldCAtPiBzY2jDtm5lciBzY2hyZWliZW4KCkRpZSBNYXRyaXggaXN0IHNlaHIgc3BhcmNlLiBGYXN0IDk0JSBkZXIgRGF0ZW4gYmVzdGVoZW4gYXVzIE5BIFdlcnRlbi4gCkRpZXMgd3VyZGUgc28gZXJ3YXJ0ZXQsIGRhIGVzIHVud2FocnNjaGVpbmxpY2ggaXN0IGRhc3MgZWluIEZpbG0gdm9uIGFsbGVuIHVzZXJzIGFraXYgYmV3ZXJ0ZXQgd2lyZCwgb2RlciBkYXNzIGVpbiBVc2VyIGFsbGUgRmlsbWUgYW5zaWVodCB1bmQgYXVjaCBiZXdlcnRldC4KCioqKgojIyBEYXRlbnJlZHVrdGlvbgpgYGB7cn0KI0RhdGEgcmVkdWN0aW9uCmRlbnNlX3JlZHVjdGlvbiA8LSBkYXRhX3JlZHVjdGlvbl9kZW5zZShNb3ZpZUxlbnNlKQpkZW5zZV91c2VyX3JlZHVjdGlvbiA8LSBkYXRhX3JlZHVjdGlvbl9kZW5zZV91c2VyKE1vdmllTGVuc2UpCnJhbmRvbV9yZWR1Y3Rpb24gPC0gZGF0YV9yZWR1Y3Rpb25fcmFuZG9tKE1vdmllTGVuc2UpCgojc2FtZSBhcyBkZW5zZSByZWR1Y3Rpb24KcmF0aW5nTWF0cml4IDwtIGRhdGFfcmVkdWN0aW9uX2RlbnNlKE1vdmllTGVuc2UpCgptYXRyaWNlcyA8LSBjKCdPcmlnaW5hbCBNYXRyaXggKE1vdmllTGVuc2UpJywgJ2RlbnNlX3JlZHVjdGlvbicsICdkZW5zZV91c2VyX3JlZHVjdGlvbicsICdyYW5kb21fcmVkdWN0aW9uJykKc3BhcnNpdGllcyA8LSBjKGdldF9zcGFyc2l0eShNb3ZpZUxlbnNlKSwgZ2V0X3NwYXJzaXR5KGRlbnNlX3JlZHVjdGlvbiksIGdldF9zcGFyc2l0eShkZW5zZV91c2VyX3JlZHVjdGlvbiksIGdldF9zcGFyc2l0eShyYW5kb21fcmVkdWN0aW9uKSkKCmRmX3NwYXJzaXR5IDwtIGRhdGEuZnJhbWUobWF0cml4ID0gbWF0cmljZXMsIHNwYXJzaXR5ID0gc3BhcnNpdGllcykKCiNQbG90IERhdGEgcmVkdWN0aW9uCmdncGxvdChkZl9zcGFyc2l0eSwgYWVzKHg9bWF0cml4LCB5ID0gc3BhcnNpdHkpKSArIAogIGdlb21fY29sKGZpbGwgPSAnc3RlZWxibHVlJykgKwogIGNvb3JkX2ZsaXAoKSArCiAgc2NhbGVfeV9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSkgKwogIGdlb21fdGV4dChhZXMobGFiZWw9cm91bmQoc3BhcnNpdHksMikpLCBoanVzdCA9IDEuMywgY29sb3IgPSAnd2hpdGUnKSArCiAgbGFicygKICAgIHRpdGxlID0gIlNwYXJzaXR5IGRlciB2ZXJzY2hpZWRlbmVuIERhdGVucmVkdWt0aW9uZW4iLAogICAgeCA9IGVsZW1lbnRfYmxhbmsoKSwgCiAgICB5ID0gIlNwYXJjaXR5IGluIFByb3plbnQiLAogICAgZmlsbCA9IGVsZW1lbnRfYmxhbmsoKQogICkgKwogIHRoZW1lX2NsYXNzaWMoKSArIAogIHRoZW1lKAogICAgdGV4dCA9IGVsZW1lbnRfdGV4dChzaXplID0gMTIpLAogICAgbGVnZW5kLnBvc2l0aW9uID0gJ2JvdHRvbScKICApCmBgYApUT0RPOiBCZXNzZXJlciBiZXNjaHJlaWIgenUgZGVuIHJlZHVrdGlvbmVuIC0gd2llc28gd2VsY2hlIHJlZHVrdGlvbmVuICsgd2llc28gZGllc2Ugc3BhcmNpdHkKRsO8ciBkaWUgZGVuc2VfcmVkdWN0aW9uIHNpbmt0IGRpZSBTcGFyc2l0eSB2b24gOTMuNjclIGF1ZiA3NS44MCUuCkbDvHIgZGllIGRlbnNlX3VzZXJfcmVkdWN0aW9uIHNpbmt0IGRpZSBTcGFyc2l0eSB2b24gOTMuNjclIGF1ZiA4OC4xOCUuCkbDvHIgZGllIHJhbmRvbV9yZWR1Y3Rpb24gYmxlaWJ0IGRpZSBTcGFyc2l0eSBwcmFrdGlzY2ggdW52ZXLDpG5kZXJ0LiBTaWUgc2lua3Qgdm9uIDkzLjY3JSBhdWYgOTIuNzUlLgoKYGBge3IgZmlnLndpZHRoID0gMjAsIGZpZy5oZWlnaHQgPSA1fQpwMSA8LSBpbWFnZShkZW5zZV9yZWR1Y3Rpb24sIG1haW4gPSAiUmF3IFJhdGluZ3MgZm9yIERlbnNlIFJlZHVjdGlvbiIpCnAyIDwtIGltYWdlKGRlbnNlX3VzZXJfcmVkdWN0aW9uLCBtYWluID0gIlJhdyBSYXRpbmdzIGZvciBEZW5zZSBVc2VyIFJlZHVjdGlvbiIpCnAzIDwtIGltYWdlKHJhbmRvbV9yZWR1Y3Rpb24sIG1haW4gPSAiUmF3IFJhdGluZ3MgZm9yIFJhbmRvbSBSZWR1Y3Rpb24iKQoKZ3JpZC5hcnJhbmdlKHAxLCBwMiwgcDMsIG5jb2wgPSAzLCBucm93ID0gMSkKYGBgClRPRE86IG1laHIgYmVzY2hyZWlidW5nCgpNYW4gc2llaHQgc2VociBrbGFyLCBkYXNzIGRpZSBtYXRyaXggbnVuIGRldXRsaWNoIHdlbmlnZXIgc3BhcnNlIGlzdC4KCgpgYGB7ciBmaWcud2lkdGggPSAxNSwgZmlnLmhlaWdodCA9IDExfQpwMSA8LSBzaG93X2NoYW5nZV9vZl9yYXRpbmdfZGlzdHJpYnV0aW9uKE1vdmllTGVuc2UsIGRlbnNlX3JlZHVjdGlvbiwgJ0bDvHIgZGVuc2VfcmVkdWN0aW9uLCBOIGFsdGUgTWF0cml4ID0gMTY2NCBGaWxtZSwgTiBuZXVlIE1hdHJpeCA9IDcwMCBGaWxtZScpCnAyIDwtIHNob3dfY2hhbmdlX29mX3JhdGluZ19kaXN0cmlidXRpb24oTW92aWVMZW5zZSwgZGVuc2VfdXNlcl9yZWR1Y3Rpb24sICdGw7xyIGRlbnNlX3VzZXJfcmVkdWN0aW9uLCBOIGFsdGUgTWF0cml4ID0gMTY2NCBGaWxtZSwgTiBuZXVlIE1hdHJpeCA9IDcwMCBGaWxtZScpCnAzIDwtIHNob3dfY2hhbmdlX29mX3JhdGluZ19kaXN0cmlidXRpb24oTW92aWVMZW5zZSwgcmFuZG9tX3JlZHVjdGlvbiwgJ0bDvHIgcmFuZG9tX3JlZHVjdGlvbiwgTiBhbHRlIE1hdHJpeCA9IDE2NjQgRmlsbWUsIE4gbmV1ZSBNYXRyaXggPSA3MDAgRmlsbWUnKQoKZ3JpZC5hcnJhbmdlKHAxLCBwMiwgcDMsIG5jb2wgPSAyLCBucm93ID0gMikKYGBgClRPRE86IGJlc2NocmVpYnVuZwoKCioqKgojIyBBbmFseXNlIMOEaG5saWNoa2VpdHNtYXRyaXgKIyMjIyAxLiBaZXJsZWdlIGRlbiByZWR1emllcnRlbiBNb3ZpZUxlbnNlIERhdGVuc2F0eiBpbiBlaW4gZGlzanVua3RlcyBUcmFpbmluZ3MtIHVuZCBUZXN0ZGF0ZW5zZXQgaW0gVmVyaMOkbHRuaXMgNDoxCmBgYHtyfQojYm90aCA8LSBzcGxpdF9kYXRhc2V0KHJhdGluZ01hdHJpeCwgMC44KQojdHJhaW4gPC0gYm90aFtbMV1dCiN0ZXN0IDwtIGJvdGhbWzJdXQoKI3ByaW50KCdUcmFpbmluZ3NkYXRlbnNldDonKQojZGltKHRyYWluKQojcHJpbnQoJycpCiNwcmludCgnVGVzdGRhdGVuc2V0OicpCiNkaW0odGVzdCkKCmUgPC0gZXZhbHVhdGlvblNjaGVtZShkZW5zZV9yZWR1Y3Rpb24sIG1ldGhvZD0ic3BsaXQiLCB0cmFpbj0wLjgsIGs9MSwgZ2l2ZW49MCkKdHJhaW4gPC0gZ2V0RGF0YShlLCAidHJhaW4iKQp0ZXN0IDwtIGdldERhdGEoZSwgJ3Vua25vd24nKQpgYGAKVE9ETzogaWdub3JlIHdhcm5pbmcgKyBldnRsLiBsw7ZzY2hlbj8KCioqKgojIyMjIDIuIFRyYWluaWVyZSBlaW4gSUJDRiBNb2RlbGwgbWl0IDMwIE5hY2hiYXJuIHVuZCBDb3NpbmUgU2ltaWxhcml0eQpgYGB7cn0KIyB0cmFpbiBJQkNGIHJlY29tbWVuZGVyCnJlYyA8LSBSZWNvbW1lbmRlcih0cmFpbiwgbWV0aG9kID0gIklCQ0YiLCBwYXJhbT1saXN0KG1ldGhvZD0iQ29zaW5lIiwgaz0zMCwgbm9ybWFsaXplID0gTlVMTCwgbmFfYXNfemVybyA9IFRSVUUpKSAjbm9ybWFsaXplID0gJ2NlbnRlcicKIyBwcmVkaWN0IHRvcCAxMCBtb3ZpZXMgZm9yIDEwMCB1c2VycwpwcmUgPC0gcHJlZGljdChyZWMsIHRlc3QsIG4gPSAxMCkKYGBgCioqKgojIyMjIDMuIEJlc3RpbW1lIGRpZSBWZXJ0ZWlsdW5nIGRlciBGaWxtZSwgd2VsY2hlIGJlaSBJQkNGIGbDvHIgcGFhcndlaXNlIMOEaG5saWNoa2VpdHN2ZXJnbGVpY2hlIHZlcndlbmRldCB3ZXJkZW4KYGBge3J9Cm1vZGVsIDwtIGdldE1vZGVsKHJlYykKY29sU3VtIDwtIGNvbFN1bXMobW9kZWwkc2ltID4gMCkKCmRmIDwtIGFzLmRhdGEuZnJhbWUoY29sU3VtKQoKIyBhZGQgaW5kZXggY29sdW1uCmRmIDwtIGNiaW5kKGl0ZW0gPSByb3duYW1lcyhkZiksIGRmKQpyb3duYW1lcyhkZikgPC0gMTpucm93KGRmKQoKZ2dwbG90KGRmLCBhZXMoeCA9IGNvbFN1bSkpICsKICBnZW9tX2hpc3RvZ3JhbShhbHBoYSA9IDEsIGZpbGwgPSAnc3RlZWxibHVlJywgYmlud2lkdGggPSAyKSArCiAgc2NhbGVfeV9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSkgKwogIHNjYWxlX3hfY29udGludW91cyhleHBhbmQgPSBjKDAsMCkpICsKICBsYWJzKAogICAgdGl0bGUgPSAiVmVydGVpbHVuZyBkZXIgQW56YWhsIMOkaG5saWNoZXIgRmlsbWUiLAogICAgIyBzdWJ0aXRsZSA9IHBhc3RlKCJOID0gIiwgbnJvdyhkZjMpLCAiIEZpbG1lIiksCiAgICB4ID0gIkFuemFobCBGaWxtZSBiZWkgZGVuZW4gZGVyIEZpbG0gYWxzIE5hY2hiYXIgYXVmdGF1Y2h0IiwgCiAgICB5ID0gIkjDpHVmaWdrZWl0IgogICkgKwogIHRoZW1lX2NsYXNzaWMoKSArCiAgdGhlbWUodGV4dCA9IGVsZW1lbnRfdGV4dChzaXplID0gMTIpCiAgKQpgYGAKVE9ETzogZ3V0ZSBiZXNjaHJlaWJ1bmcKCioqKgojIyMjIDQuIEJlc3RpbW1lIGRpZSBGaWxtZSwgZGllIGFtIGjDpHVmaWdzdGVuIGluIGRlciBDb3NpbmUtw4RobmxpY2hrZWl0c21hdHJpeCBhdWZ0YXVjaGVuIHVuZCBhbmFseXNpZXJlIGRlcmVuIFZvcmtvbW1lbiB1bmQgUmF0aW5ncyBpbSByZWR1emllcnRlbiBEYXRlbnNhdHoKYGBge3J9CmRmMSA8LSBkZiAlPiUgYXJyYW5nZShkZXNjKGNvbFN1bSkpICU+JSBoZWFkKDEwKQoKZ2dwbG90KGRmMSwgYWVzKHggPSBjb2xTdW0sIHkgPSByZW9yZGVyKGl0ZW0sICtjb2xTdW0pKSkrCiAgZ2VvbV9jb2woYWxwaGEgPSAxLCBmaWxsID0gJ3N0ZWVsYmx1ZScpKwogIHNjYWxlX3lfZGlzY3JldGUoZXhwYW5kID0gYygwLDApKSArCiAgc2NhbGVfeF9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSkgKwogIGdlb21fdGV4dChhZXMobGFiZWw9cm91bmQoY29sU3VtLDIpKSwgaGp1c3QgPSAxLjMsIGNvbG9yID0gJ3doaXRlJykgKwogIGxhYnMoCiAgICB0aXRsZSA9ICJIw6R1Zmlnc3RlIEZpbG1lIGluIENvc2luZS3DhGhubGljaGtlaXRzbWF0cml4IiwKICAgIHkgPSBlbGVtZW50X2JsYW5rKCksCiAgICB4ID0gIkFuemFobCBGaWxtZSBpbiBkZXJlbiBOYWNoYmFyc2NoYWZ0IGRlciBGaWxtIGlzdCIKICApICsKICB0aGVtZV9jbGFzc2ljKCkgKwogIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF9ibGFuaygpLAogICAgICAgIGF4aXMudGlja3MueCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICBheGlzLmxpbmUueCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMikgIyB0ZXh0IHNpemUKICApCmBgYApUT0RPOiBCZXNjaHJlaWJ1bmcKCmBgYHtyfQp0b3AxMCA8LSBhcy5saXN0KGRmMSkkaXRlbQoKZGF0YSA8LSBhcyhyYXRpbmdNYXRyaXgsICJkYXRhLmZyYW1lIikKZGF0YTEgPC0gZGF0YSAlPiUKICBncm91cF9ieShpdGVtKSAlPiUKICBzdW1tYXJpemUobWVhbl9yYXRpbmcgPSBtZWFuKHJhdGluZykpICU+JQogIGFycmFuZ2UoZGVzYyhtZWFuX3JhdGluZykpICU+JQogIG11dGF0ZShjYXRlZ29yeSA9IGlmZWxzZShpdGVtICVpbiUgdG9wMTAsICdIw6R1Zmlnc3RlIDEwIEZpbG1lJywgJ1Jlc3RsaWNoZSBGaWxtZScpKQoKZ2dwbG90KGRhdGExLCBhZXMoeCA9IG1lYW5fcmF0aW5nLCBmaWxsID0gY2F0ZWdvcnkpKSArCiAgZ2VvbV9kZW5zaXR5KGFscGhhID0gMC41LCBidyA9IDAuMDUpICsKICBzY2FsZV95X2NvbnRpbnVvdXMoZXhwYW5kID0gYygwLDApKSArCiAgc2NhbGVfeF9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSkgKwogIGxhYnMoCiAgICB0aXRsZSA9ICJWZXJ0ZWlsdW5nIG1pdHRsZXJlIEt1bmRlbnJhdGluZ3MgcHJvIEZpbG0iLAogICAgeCA9ICJEdXJjaHNjaG5pdHRsaWNoZSBCZXdlcnR1bmciLAogICAgeSA9ICJEaWNodGUiLAogICAgZmlsbCA9IGVsZW1lbnRfYmxhbmsoKQogICkgKwogIHRoZW1lX2NsYXNzaWMoKSArCiAgdGhlbWUoCiAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMiksCiAgICBsZWdlbmQucG9zaXRpb24gPSBjKC4xNCwgLjkzKQogICkKYGBgClRPRE86IG1laHIgYmVzY2hyZWlidW5nCkVzIGbDpGxsdCBhdWYsIGRhc3MgZGllIGjDpHVmaWdzdGVuIEZpbG1lIGFsbGdlbWVpbiBzZWhyIGd1dCBiZXdlcnRldCB3ZXJkZW4uCgoqKioKIyNBbmFseXNlIFRvcC1OIExpc3RlbiAtIElCQ0YgdnMuIFVCQ0YKIyMjIzEuQmVyZWNobmUgVG9wLTE1IEVtcGZlaGx1bmdlbiBmw7xyIFRlc3RrdW5kZW4gbWl0IElCQ0YgdW5kIFVCQ0YKYGBge3J9CnJlY19pYmNmIDwtIFJlY29tbWVuZGVyKHRyYWluLCBtZXRob2QgPSAiSUJDRiIsIHBhcmFtPWxpc3QobWV0aG9kPSJDb3NpbmUiLCBrPTMwLCBub3JtYWxpemUgPSBOVUxMLCBuYV9hc196ZXJvID0gVFJVRSkpCnRvcG5faWJjZiA8LSBwcmVkaWN0KHJlY19pYmNmLCB0ZXN0LCBuID0gMTUpCnRvcG5faWJjZl9saXN0IDwtIGFzKHRvcG5faWJjZiwgImxpc3QiKQp0b3BuX2liY2ZfZGYgPC0gYXMuZGF0YS5mcmFtZShkby5jYWxsKHJiaW5kLCB0b3BuX2liY2ZfbGlzdCkpCgpyZWNfdWJjZiA8LSBSZWNvbW1lbmRlcih0cmFpbiwgbWV0aG9kID0gIlVCQ0YiLCBwYXJhbT1saXN0KG1ldGhvZD0iQ29zaW5lIiwgbm9ybWFsaXplID0gTlVMTCkpCnRvcG5fdWJjZiA8LSBwcmVkaWN0KHJlY191YmNmLCB0ZXN0LCBuID0gMTUpCnRvcG5fdWJjZl9saXN0IDwtIGFzKHRvcG5fdWJjZiwgImxpc3QiKQp0b3BuX3ViY2ZfZGYgPC0gYXMuZGF0YS5mcmFtZShkby5jYWxsKHJiaW5kLCB0b3BuX3ViY2ZfbGlzdCkpCmBgYAoKKioqCiMjIyMyLlZlcmdsZWljaGUgZGllIFRvcC0xNSBFbXBmZWhsdW5nZW4gdW5kIGRlcmVuIFZlcnRlaWx1bmcgdW5kIGRpc2t1dGllcmUgR2VtZWluc2Fta2VpdGVuIHVuZCBVbnRlcnNjaGllZGUgendpc2NoZW4gSUJDRiB1bmQgVUJDRiBmw7xyIGFsbGUgVGVzdGt1bmRlbi4KYGBge3IgZmlnLndpZHRoID0gMTUsIGZpZy5oZWlnaHQgPSA2fQojY29tcGFyZSBtb3N0IG9jY3VycmluZyBpdGVtcwoKaWJjZl90b3AgPC0gaGVhZChzb3J0KGNvbENvdW50cyh0b3BuX2liY2YpLCBkZWNyZWFzaW5nID0gVFJVRSkpCmliY2ZfdG9wX2RmIDwtIGFzLmRhdGEuZnJhbWUoaWJjZl90b3ApCmliY2ZfdG9wX2RmIDwtIHRpYmJsZTo6cm93bmFtZXNfdG9fY29sdW1uKGliY2ZfdG9wX2RmLCAibW92aWVzIikKbmFtZXMoaWJjZl90b3BfZGYpW25hbWVzKGliY2ZfdG9wX2RmKSA9PSAnaWJjZl90b3AnXSA8LSAnbl9hcHBlYXJhbmNlcycKCgp1YmNmX3RvcCA8LSBoZWFkKHNvcnQoY29sQ291bnRzKHRvcG5fdWJjZiksIGRlY3JlYXNpbmcgPSBUUlVFKSkKdWJjZl90b3BfZGYgPC0gYXMuZGF0YS5mcmFtZSh1YmNmX3RvcCkKdWJjZl90b3BfZGYgPC0gdGliYmxlOjpyb3duYW1lc190b19jb2x1bW4odWJjZl90b3BfZGYsICJtb3ZpZXMiKQpuYW1lcyh1YmNmX3RvcF9kZilbbmFtZXModWJjZl90b3BfZGYpID09ICd1YmNmX3RvcCddIDwtICduX2FwcGVhcmFuY2VzJwoKcDEgPC0gcGxvdF9tb3N0X29jY19pdGVtKGliY2ZfdG9wX2RmLCAnaWJjZicpCnAyIDwtIHBsb3RfbW9zdF9vY2NfaXRlbSh1YmNmX3RvcF9kZiwgJ3ViY2YnKQoKZ3JpZC5hcnJhbmdlKHAxLCBwMiwgbmNvbCA9IDIsIG5yb3cgPSAxKQpgYGAKQXVmZsOkbGxpZyBpc3QsIGRhc3MgaW0gVUJDRiBkaWUgRmlsbWUsIHdlbGNoZSBhbSBow6R1Zmlnc3RlbiBpbiBkZW4gVG9wLTE1IEVtcGZlaGx1bmdlbiBhdWZ0YXVjaGVuLCB3ZXNlbnRsaWNoIMO2ZnRlcnMgdm9ya29tbWVuIGFscyBkaWVzZSwgZGllIGltIElCQ0YgYWxzIGFtIG1laXN0IHZvcmtvbW1lbmRlIEZpbG1lIGRlZmluaWVydCBzaW5kLiBFYmVuZmFsbHMgYXVmZmFsbGVuZCBpc3QsIGRhc3MgZGllIGJlaWRlbiBSZWNvbW1lbmRlciBzZWhyIHZlcnNjaGllZGVuZSBWb3JzY2hsw6RnZSBtYWNoZW4uIEbDvHIgZGllIG1laXN0IHZvcmtvbW1lbmRlbiBGaWxtZSBpbiBkZW4gVG9wTkxpc3RlbiBnaWJ0IGVzIGhpZXIga2VpbmUgw5xiZXJzY2huZWlkdW5nLgoKYGBge3J9CiNnZXQgZGlzdHJpYnV0aW9uIG9mIGludGVyc2VjdCBmb3IgZWFjaCB1c2VyCiNpbnRlcnNlY3Qgb2YgdG9wIDE1IHJlY29tbWVuZGF0aW9ucyBJQkNGIHZzIFVCQ0YKI2xpc3RfY29tcF9pYmNmX3ViY2YgPC0gdmVjdG9yKG1vZGUgPSAibGlzdCIsIGxlbmd0aCA9IGxlbmd0aCh0b3BuX2liY2ZfbGlzdCkpCmxpc3RfY29tcF9pYmNmX3ViY2YgPC0gbGlzdCgpCmZvciAobiBpbiAxOmxlbmd0aCh0b3BuX2liY2ZfbGlzdCkpIHsKICBpbnRlcnNlY3Rpb24gPC0gbGVuZ3RoKGludGVyc2VjdCh1bmxpc3QodG9wbl9pYmNmX2xpc3Rbbl0pLCB1bmxpc3QodG9wbl91YmNmX2xpc3Rbbl0pKSkgLyAxNQogIGxpc3RfY29tcF9pYmNmX3ViY2YgPC0gYXBwZW5kKGxpc3RfY29tcF9pYmNmX3ViY2YsIGludGVyc2VjdGlvbikKfQoKY29tcF9pYmNmX3ViY2YgPC0gZGF0YS5mcmFtZShtYXRyaXgodW5saXN0KGxpc3RfY29tcF9pYmNmX3ViY2YpLCBucm93PWxlbmd0aChsaXN0X2NvbXBfaWJjZl91YmNmKSwgYnlyb3c9VFJVRSkpCmNvbG5hbWVzKGNvbXBfaWJjZl91YmNmKSA8LSBjKCdpbnRlcnNlY3QnKQpjb21wX2liY2ZfdWJjZiA8LSBjb21wX2liY2ZfdWJjZiAlPiUgZ3JvdXBfYnkoaW50ZXJzZWN0KSAlPiUgc3VtbWFyaXNlKGNvdW50ID0gbigpKSAlPiUgdW5ncm91cCgpCmNvbXBfaWJjZl91YmNmJGludGVyc2VjdCA8LSBhcy5jaGFyYWN0ZXIocm91bmQoY29tcF9pYmNmX3ViY2YkaW50ZXJzZWN0LCAyKSkKCmdncGxvdChjb21wX2liY2ZfdWJjZiwgYWVzKHggPSBpbnRlcnNlY3QsIHkgPSBjb3VudCkpICsKICBnZW9tX2NvbChhbHBoYSA9IDEsIGZpbGwgPSAnc3RlZWxibHVlJykgKwogIGdlb21fdGV4dChhZXMobGFiZWw9Y291bnQpLCB2anVzdD0xLjUsIGNvbG9yID0gJ3doaXRlJykgKwogIHNjYWxlX3lfY29udGludW91cyhleHBhbmQgPSBjKDAsMCkpICsKICBsYWJzKAogICAgdGl0bGUgPSAiVmVydGVpbHVuZyBkZXIgw7xiZXJzY2huZWlkdW5nIGRlciBlbXBmb2hsZW5lbiBGaWxtZSIsCiAgICAjIHN1YnRpdGxlID0gcGFzdGUoIk4gPSAiLCBucm93KGRmMyksICIgRmlsbWUiKSwKICAgIHggPSAiw5xiZXJzY2huZWlkdW5nIGluICUiLCAKICAgIHkgPSAiSMOkdWZpZ2tlaXQiCiAgKSArCiAgdGhlbWVfY2xhc3NpYygpICsKICB0aGVtZSh0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMikKICApCmBgYApUT0RPOiBiZXNjaHJlaWIKCioqKgojIyBBbmFseXNlIFRvcC1OIExpc3RlbiAtIFJhdGluZ3MKIyMjIyBWZXJnbGVpY2hlIGRlbiBBbnRlaWwgw7xiZXJlaW5zdGltbWVuZGVyIEVtcGZlaGx1bmdlbiBkZXIgVG9wLTE1IExpc3RlIGbDvHIgSUJDRiB2cyBVQkNGLCBiZWlkZSBtaXQgb3JkaW5hbGVtIFJhdGluZyB1bmQgQ29zaW5lIFNpbWlsYXJpdHkgZsO8ciBhbGxlIFRlc3RrdW5kZW4KYGBge3J9CiNpYmNmIHJlY29tbWVuZGVyIHdpdGggSmFjY2FyZCBzaW1pbGFyaXR5CnJlY19pYmNmX2phYyA8LSBSZWNvbW1lbmRlcih0cmFpbiwgbWV0aG9kID0gIklCQ0YiLCBwYXJhbT1saXN0KG1ldGhvZD0iSmFjY2FyZCIsIGs9MzAsIG5vcm1hbGl6ZSA9IE5VTEwsIG5hX2FzX3plcm8gPSBUUlVFKSkKdG9wbl9pYmNmX2phYyA8LSBwcmVkaWN0KHJlY19pYmNmX2phYywgdGVzdCwgbiA9IDE1KQp0b3BuX2liY2ZfamFjX2xpc3QgPC0gYXModG9wbl9pYmNmX2phYywgImxpc3QiKQoKI3ViY2YgcmVjb21tZW5kZXIgd2l0aCBKYWNjYXJkIHNpbWlsYXJpdHkKcmVjX3ViY2ZfamFjIDwtIFJlY29tbWVuZGVyKHRyYWluLCBtZXRob2QgPSAiVUJDRiIsIHBhcmFtPWxpc3QobWV0aG9kPSJKYWNjYXJkIiwgbm9ybWFsaXplID0gTlVMTCkpCnRvcG5fdWJjZl9qYWMgPC0gcHJlZGljdChyZWNfdWJjZl9qYWMsIHRlc3QsIG4gPSAxNSkKdG9wbl91YmNmX2phY19saXN0IDwtIGFzKHRvcG5fdWJjZl9qYWMsICJsaXN0IikKCmNvbXBhcmlzb24gPC0gbWF0cml4KG5jb2wgPSAyLCBucm93ID0gMykKCiNpbnRlcnNlY3Qgb2YgdG9wIDE1IHJlY29tbWVuZGF0aW9ucyBJQkNGIHZzIFVCQ0YgY29zaW5lIHNpbWlsYXJpdHkKY29tcF9vcmRfY29zPC0gMApmb3IgKG4gaW4gMTpsZW5ndGgodG9wbl9pYmNmX2xpc3QpKSB7CiAgaW50ZXJzZWN0aW9uIDwtIGxlbmd0aChpbnRlcnNlY3QodW5saXN0KHRvcG5faWJjZl9saXN0W25dKSwgdW5saXN0KHRvcG5fdWJjZl9saXN0W25dKSkpIC8gMTUKICBjb21wX29yZF9jb3MgPC0gY29tcF9vcmRfY29zICsgaW50ZXJzZWN0aW9uCn0KY29tcGFyaXNvblsxLDFdIDwtICdpYmNmIGNvcyAtIHViY2YgY29zJwpjb21wYXJpc29uWzEsMl0gPC0gcm91bmQoY29tcF9vcmRfY29zIC8gbGVuZ3RoKHRvcG5faWJjZl9saXN0KSwgMikKCgojaW50ZXJzZWN0IG9mIHRvcCAxNSByZWNvbW1lbmRhdGlvbnMgSUJDRiB2cyBVQkNGIEphY2NhcmQgc2ltaWxhcml0eQpjb21wX2Jpbl9qYWM8LSAwCmZvciAobiBpbiAxOmxlbmd0aCh0b3BuX2liY2ZfamFjX2xpc3QpKSB7CiAgaW50ZXJzZWN0aW9uIDwtIGxlbmd0aChpbnRlcnNlY3QodW5saXN0KHRvcG5faWJjZl9qYWNfbGlzdFtuXSksIHVubGlzdCh0b3BuX3ViY2ZfamFjX2xpc3Rbbl0pKSkgLyAxNQogIGNvbXBfYmluX2phYyA8LSBjb21wX2Jpbl9qYWMgKyBpbnRlcnNlY3Rpb24KfQpjb21wYXJpc29uWzIsMV0gPC0gJ2liY2YgY29zIC0gdWJjZiBqYWMnCmNvbXBhcmlzb25bMiwyXSA8LSByb3VuZChjb21wX2Jpbl9qYWMgLyBsZW5ndGgodG9wbl9pYmNmX2phY19saXN0KSwgMikKCiNpbnRlcnNlY3Qgb2YgdG9wIDE1IHJlY29tbWVuZGF0aW9ucyBVQkNGIENvc2luZSBTaW1pbGFyaXR5IHZzIFVCQ0YgSmFjY2FyZCBzaW1pbGFyaXR5CmNvbXBfY29zX2phYzwtIDAKZm9yIChuIGluIDE6bGVuZ3RoKHRvcG5fdWJjZl9qYWNfbGlzdCkpIHsKICBpbnRlcnNlY3Rpb24gPC0gbGVuZ3RoKGludGVyc2VjdCh1bmxpc3QodG9wbl91YmNmX2phY19saXN0W25dKSwgdW5saXN0KHRvcG5fdWJjZl9saXN0W25dKSkpIC8gMTUKICBjb21wX2Nvc19qYWMgPC0gY29tcF9jb3NfamFjICsgaW50ZXJzZWN0aW9uCn0KY29tcGFyaXNvblszLDFdIDwtICd1YmNmIGNvcyAtIHViY2YgamFjJwpjb21wYXJpc29uWzMsMl0gPC0gcm91bmQoY29tcF9jb3NfamFjIC8gbGVuZ3RoKHRvcG5fdWJjZl9qYWNfbGlzdCksIDIpCgpjb21wYXJpc29uIDwtIGRhdGEuZnJhbWUoY29tcGFyaXNvbikKY29tcGFyaXNvbgoKZ2dwbG90KGNvbXBhcmlzb24sIGFlcyh4ID0gWDEsIHkgPSBYMikpICsKICBnZW9tX2NvbChhbHBoYSA9IDEsIGZpbGwgPSAnc3RlZWxibHVlJykgKwogICNnZW9tX3RleHQoYWVzKGxhYmVsPWNvdW50KSwgdmp1c3Q9MS41LCBjb2xvciA9ICd3aGl0ZScpICsKICBzY2FsZV95X2Rpc2NyZXRlKGV4cGFuZCA9IGMoMCwwKSkgKwogIGxhYnMoCiAgICB0aXRsZSA9ICJWZXJ0ZWlsdW5nIGRlciDDvGJlcnNjaG5laWR1bmcgZGVyIGVtcGZvaGxlbmVuIEZpbG1lIiwKICAgICMgc3VidGl0bGUgPSBwYXN0ZSgiTiA9ICIsIG5yb3coZGYzKSwgIiBGaWxtZSIpLAogICAgeCA9ICLDnGJlcnNjaG5laWR1bmcgaW4gJSIsIAogICAgeSA9ICJIw6R1Zmlna2VpdCIKICApICsKICB0aGVtZV9jbGFzc2ljKCkgKwogIHRoZW1lKHRleHQgPSBlbGVtZW50X3RleHQoc2l6ZSA9IDEyKQogICkKYGBgClRPRE86IEZvckxvb3AKVE9ETzogZsO8ciBhbGxlIERhdGVucmVkdWt0aW9uZW4gKyAzIHBsb3RzIGluIGdyaWQgKHdpZHRoID0gMTUpCgoqKioKIyNBbmFseXNlIFRvcC1OIExpc3RlbiAtIElCQ0YgdnMgU1ZECiMjIyMxLlZlcmdsZWljaGUgd2llIHNpY2ggZGVyIEFudGVpbCDDvGJlcmVpbnN0aW1tZW5kZXIgRW1wZmVobHVuZ2VuIGRlciBUb3AtMTUgTGlzdGUgZsO8ciBJQkNGIHZzIHZlcnNjaGllZGVuZSBTVkQgTW9kZWxsZSB2ZXLDpG5kZXJ0LCB3ZW5uIGRpZSBBbnphaGwgZGVyIFNpbmd1bMOkcndlcnRlIGbDvHIgU1ZEIHZvbiAxMCBhdWYgMjAsIDMwLCA0MCwgNTAgdmVyw6RuZGVydCB3aXJkCmBgYHtyfQojZGVuc2VfcmVkdWN0aW9uLCBkZW5zZV91c2VyX3JlZHVjdGlvbiwgcmFuZG9tX3JlZHVjdGlvbgoKZGF0YXNldHMgPSBjKGRlbnNlX3JlZHVjdGlvbiwgZGVuc2VfdXNlcl9yZWR1Y3Rpb24sIHJhbmRvbV9yZWR1Y3Rpb24pCmRhdGFzZXRuYW1lcyA9IGMoJ2RlbnNlX3JlZHVjdGlvbicsICdkZW5zZV91c2VyX3JlZHVjdGlvbicsICdyYW5kb21fcmVkdWN0aW9uJykKayA9IGMoMTAsIDIwLCAzMCwgNDAsIDUwKQpkZW5zZV9yZWR1Y3Rpb24KCm91dHB1dCA8LSBkYXRhLmZyYW1lKCdjb21wYXJpc29uJyA9IGNoYXJhY3RlcigpLCAnaW50ZXJzZWN0aW9uJyA9IG51bWVyaWMoKSwgJ2RhdGFzZXQnID0gY2hhcmFjdGVyKCkpCmNvbG5hbWVzKG91dHB1dCkgPC0gYygnY29tcGFyaXNvbicsICdpbnRlcnNlY3Rpb24nLCAnZGF0YXNldCcpCgpmb3IgKGQgaW4gMTpsZW5ndGgoZGF0YXNldHMpKXsKICBlIDwtIGV2YWx1YXRpb25TY2hlbWUoZGF0YXNldHNbW2RdXSwgbWV0aG9kPSJzcGxpdCIsIHRyYWluPTAuOCwgaz0xLCBnaXZlbj0wKQogIHRyYWluIDwtIGdldERhdGEoZSwgInRyYWluIikKICB0ZXN0IDwtIGdldERhdGEoZSwgJ3Vua25vd24nKQogIAogIGZvciAobiBpbiBrKXsKICAgIHJlY19zdmQgPC0gUmVjb21tZW5kZXIodHJhaW4sIG1ldGhvZCA9ICJTVkQiLCBwYXJhbT1saXN0KGsgPSBuKSkKICAgIHRvcG5fc3ZkIDwtIHByZWRpY3QocmVjX3N2ZCwgdGVzdCwgbiA9IDE1KQogICAgdG9wbl9zdmRfbGlzdCA8LSBhcyh0b3BuX3N2ZCwgImxpc3QiKQogIAogICAgY29tcF9pYmNmX3N2ZCA8LSAwCiAgICBmb3IgKGkgaW4gMTpsZW5ndGgodG9wbl9pYmNmX2xpc3QpKSB7CiAgICAgIGludGVyc2VjdGlvbiA8LSBsZW5ndGgoaW50ZXJzZWN0KHVubGlzdCh0b3BuX2liY2ZfbGlzdFtpXSksIHVubGlzdCh0b3BuX3N2ZF9saXN0W2ldKSkpIC8gMTUKICAgICAgY29tcF9pYmNmX3N2ZCA8LSBjb21wX2liY2Zfc3ZkICsgaW50ZXJzZWN0aW9uCiAgICB9CiAgICBvdXQgPC0gYyhwYXN0ZSgnSUJDRiB2cy4gU1ZEJywgbiksIHJvdW5kKGNvbXBfaWJjZl9zdmQgLyBsZW5ndGgodG9wbl9pYmNmX2xpc3QpLCBkaWdpdHMgPSA0KSwgYXMuY2hhcmFjdGVyKGRhdGFzZXRuYW1lc1tbZF1dKSkKICAgIG91dHB1dFtucm93KG91dHB1dCkgKyAxLF0gPSBvdXQKICAgIH0KfQoKb3V0cHV0CgpnZ3Bsb3Qob3V0cHV0LCBhZXMoeCA9IGNvbXBhcmlzb24sIHkgPSBpbnRlcnNlY3Rpb24sIGZpbGwgPSBkYXRhc2V0KSkgKwogIGdlb21fY29sKGFscGhhID0gMSwgcG9zaXRpb24gPSBwb3NpdGlvbl9kb2RnZSgpKSArCiAgI2dlb21fdGV4dChhZXMobGFiZWw9Y291bnQpLCB2anVzdD0xLjUsIGNvbG9yID0gJ3doaXRlJykgKwogIHNjYWxlX3lfZGlzY3JldGUoZXhwYW5kID0gYygwLDApKSArCiAgbGFicygKICAgIHRpdGxlID0gIlZlcnRlaWx1bmcgZGVyIMO8YmVyc2NobmVpZHVuZyBkZXIgZW1wZm9obGVuZW4gRmlsbWUiLAogICAgIyBzdWJ0aXRsZSA9IHBhc3RlKCJOID0gIiwgbnJvdyhkZjMpLCAiIEZpbG1lIiksCiAgICB4ID0gIsOcYmVyc2NobmVpZHVuZyBpbiAlIiwgCiAgICB5ID0gIkjDpHVmaWdrZWl0IgogICkgKwogIHRoZW1lX2NsYXNzaWMoKSArCiAgdGhlbWUodGV4dCA9IGVsZW1lbnRfdGV4dChzaXplID0gMTIpLAogICAgICAgIGF4aXMudGV4dC54ID0gZWxlbWVudF90ZXh0KGFuZ2xlID0gNjAsIGhqdXN0ID0gMSkKICApCmBgYAoKClRPRE86IGJlc2NocmVpYgoKKioqCiMjIFdhaGwgZGVzIG9wdGltYWxlbiBSZWNvbW1lbmRlcnMKIyMjIyBWZXJ3ZW5kZSBmw7xyIGRpZSBFdmFsdWllcnVuZyAxMC1mYWNoZSBLcmV1enZhbGlkaWVydW5nLAoKYGBge3IgZWNobz1GQUxTRSwgY2FjaGU9RkFMU0UsIHJlc3VsdHM9RkFMU0UsIGNvbW1lbnQ9RkFMU0UsIHdhcm5pbmc9RkFMU0UsIG1lc3NhZ2U9RkFMU0UsIGZpZy53aWR0aCA9IDE1LCBmaWcuaGVpZ2h0ID0gMTB9CmV2YWx1YXRlX21vZGVsKCkKYGBgCkFscyBlcnN0ZXMgc3RlbGx0ZSBzaWNoIGRpZSBGcmFnZSwgb2IgcHJlY2lzaW9uLCByZWNhbGwsIG9kZXIgZWluIGtvbWJpbmllcnRlciBGMS1TY29yZSBhbHMgcGVyZm9ybWFuY2UgTWV0cmlrIGdld8OkaGx0IHdlcmRlbiBzb2xsdGUuIFByZWNpc2lvbiBpc3QgdW1nZWtlaHJ0IHByb3BvcnRpb25hbCB6dSBmYWxzZSBwb3NpdGl2ZSwgcmVjYWxsIHp1IGZhbHNlIG5lZ2F0aXZlIFZvcmF1c3NhZ2VuLiBEYSBlcyBpbiBkaWVzZW0gRmFsbCB3aWNodGlnZXIgaXN0LCBkaWUgZ2VtYWNodGVuIEVtcGZlaGx1bmdlbiBrb3JyZWt0IHZvcmF1c3p1c2FnZW4sIHd1cmRlIFByZWNpc2lvbiBhbHMgUGVyZm9ybWFuY2UgTWV0cmlrIGRlZmluaWVydC4gQWxzIHp3ZWl0ZSBXYWhsIHfDvHJkZW4gd2lyIGF1ZiBkZW4gRjEtU2NvcmUgenVyw7xja2dncmVpZmVuLiBEaWVzZXIgc2V0enQgc2ljaCBhdXMgZGVyIEtvbWJpbmF0aW9uIGJlaWRlciBQZXRyaWtlbiBwcmVjaXNpb24gdW5kIHJlY2FsbCB6dXNhbW1lbi4KCkRlciBQYXJhbWV0ZXIgZ29vZFJhdGluZyBzdGVsbHQgZGllIGJpbsOkcmUgR3JlbnplIGRhciwgYmVpIHdlbGNoZXIgZWluIHJhdGluZyBhbHMgInBvc2l0aXYiIGJlemVpY2huZXQgd2VyZGVuIGthbm4uIFdpcmQgZGVyIFdlcnQgaMO2aGVyIGdlc2V0enQsIHNpbmt0IGRpZSBwcmVjaXNpb24gdW5kIGRlciByZWNhbGwgc3RlaWd0LiBJbiBkaWVzZXIgTW9kZWxsb3B0aW1pZXJ1bmcgd3VyZGUgZGVmaW5pZXJ0LCBkYXNzIGFsbGUgUmF0aW5ncyBhYiAzIGFscyBwb3NpdGl2IGtsYXNzaWVydCB3ZXJkZW4gc29sbHRlbi4KCkluIGRpZXNlciBHcmFmaWsgaXN0IGRpZSBwcmVjaXNpb24gZGVyIG5vdmVsdHkgZGVyIHRyYWluaWVydGVuIE1vZGVsbGUgZ2VnZW7DvGJlcmdlc3RlbGx0LiBEYWJlaSB3dXJkZSBqZWRlcyBNb2RlbGwgZsO8ciBuLXJlY29tbWVuZGF0aW9ucyB0cmFpbmllcnQgdW5kIGRhcmdlc3RlbGx0LiBFcyB3dXJkZSAxMCBmb2xkIGNyb3NzIHZhbGlkYXRpb24gdmVyd2VuZGV0LiBEaWUgZGFyZ2VzdGVsbHRlbiBXZXJ0ZSB2aXN1YWxpc2llcmVuIGRhcyBhcml0aG1ldGlzY2hlIE1pdHRlbCBkZXIgU2NvcmVzIGF1ZiBkZW4gamV3ZWlscyAxMCBUZXN0ZGF0ZW5zw6R0emVuLiBEYWR1cmNoIGvDtm5uZW4gZGllIE1vZGVsbGUgdW5kIFBhcmFtZXRlciB1bmFiaMOkbmdpZyB2b24gZGVyIFN0cnVrdHVyIGRlciBEYXRlbiBtaXRlaW5hbmRlciB2ZXJnbGljaGVuIHdlcmRlbi4KCkFscyBlcnN0ZXMgd3VyZGUgc2ljaHRiYXIsIGRhc3MgZGllIE1vZGVsbHdhaGwgbWVociBFaW5mbHVzcyBhdWYgZGllIHByZWNpc2lvbiBkZXMgTW9kZWxsIGhhdHRlIGFscyBkaWUgbi1yZWNvbW1lbmRhdGlvbnMuIERlc2hhbGIgd3VyZGUgbnVyIFNWRCB1bmQgcG9wdWxhciBmw7xyIHdlaXRlcmUgSHlwZXJwYXJhbWV0ZXJvcHRpbWllcnVuZyBhbmdlc2NoYXV0LgoKRGFzIFNWRCBNb2RlbGwgd3VyZGUgaGllciBmw7xyIHZlcnNjaGllZGVuZSBrJ3MgdHJhaW5pZXJ0LiBEYWJlaSB3dXJkZSBrbGFyLCBkYXNzIGVpbiBrfjUgZGllIGJlc3RlIHByZWNpc2lvbiB2b3JhdXNzYWd0LiBKZWRvY2gga29tbXQgZGFzIE1vZGVsbCBuaWNodCBhbm7DpGhlcm5kIGFuIGRpZSBwcmVjaXNpb24gdm9uIHBvcHVsYXIgaGVyYW4uCgpEYXMgYmVzdGUgZGFyYXVzIHJlc3VsdGllcmVuZGUgTW9kZWxsIGlzdCBpbiBkZW0gRmFsbGUgInBvcHVsYXIgaXRlbXMiIG1pdCBuPTEwIFZvcmF1c3NhZ2VuLgoKCgpEYXMgcG9wdWxhciBNb2RlbGwgYmVzaXR6dCBrZWluZSBIeXBlcnBhcmFtZXRlciBmw7xyIGRpZSBPcHRpbWllcnVuZy4KRGVzaGFsYiB3aXJkIGhpZXIgU1ZEIGJlesO8Z2xpY2ggSHlwZXJwYXJhbWV0ZXIgayB1bmQgbiBpbSBEZXRhaWwgb3B0aW1pZXJ0LgoKYGBge3IgZWNobz1GQUxTRSwgY2FjaGU9RkFMU0UsIHJlc3VsdHM9RkFMU0UsIGNvbW1lbnQ9RkFMU0UsIHdhcm5pbmc9RkFMU0UsIG1lc3NhZ2U9RkFMU0UsIGZpZy53aWR0aCA9IDE1LCBmaWcuaGVpZ2h0ID0gMTB9CgpoeXBlcl9wYXJhbV9zdmQoc2VxKGZyb209MiwgdG89MTAsIGJ5PTEpKQoKYGBgCgpGw7xyIGRhcyBNb2RlbGwgU1ZEIGlzdCBkaWUgUHJlY2lzaW9uIGFtIGJlc3Rlbiwgd2VubiBrPTQgaXN0IHVuZCBuPTEwLiAKWnVkZW0gd3VyZGUgZmVzdGdlc3RlbGx0LCBkYXNzIGplIG5hY2ggU2VlZCBQb3NpdGlvbiBrPTUgYmVzc2VyIHNlaW4ga2Fubi4KRGllIHByZWNpc2lvbiBkZXMgTW9kZWxscyBtaXQgb3B0aW1pZXJ0ZW4gSHlwZXJwYXJhbWV0ZXIgaXN0IGltbWVybm9jaCB0aWVmZXIsIGFscyBkaWUgZGVzIHBvcHVsYXIgTW9kZWxscy4KCgoqKioKIyMgSW1wbGVtZW50aWVydW5nIMOEaG5saWNoa2VpdHNtYXRyaXgKCkFscyBlcnN0ZXMgd2lyZCBoaWVyIGVpbiBzYW1wbGUgYXVzIDEwMCB6dWbDpGxsaWcgZ2V3w6RodGVuIEZpbG1lbiBnZXpvZ2VuLgoKCmBgYHtyfQoKIyByZWR1Y2Ugc2FtcGxlcyB0byAxMDAgdXNlcnMKc2FtcGxlX3NpbSA8LSBzYW1wbGVfc2ltaWxhcml0eShtb3ZpZXMpCiMgZ2VuZXJhdGUgbWF0cml4IGVxdWl2YWxlbnQKc2FtcGxlX3NpbV9tYXRyaXggPC0gYXMoc2FtcGxlX3NpbSwgJ21hdHJpeCcpCiMgY29udmVydCBiYWNrIHRvIHJlYWwgcmF0aW5nIG1hdHJpeApzYW1wbGVfc2ltX3JhdGluZyA8LSBhcyhzYW1wbGVfc2ltLCAicmVhbFJhdGluZ01hdHJpeCIpCnNhbXBsZV9zaW1fcmF0aW5nX25vcm0gPC0gbm9ybWFsaXplKHNhbXBsZV9zaW1fcmF0aW5nKQpzYW1wbGVfc2ltX3dpZGVfbm9ybSA8LSBhcyhzYW1wbGVfc2ltX3JhdGluZ19ub3JtLCAnbWF0cml4JykKIyBjcmVhdGUgd2lkZSB2ZXJzaW9ud2lkZSB2ZXJzaW9uCnNhbXBsZV9zaW1fd2lkZSA8LSBwaXZvdF93aWRlcigKICBzYW1wbGVfc2ltLAogIGlkX2NvbHMgPSB1c2VyLAogIG5hbWVzX2Zyb20gPSBpdGVtLAogIHZhbHVlc19mcm9tID0gcmF0aW5nLAogIHZhbHVlc19maWxsID0gTlVMTCwKKQoKc2FtcGxlX3NpbV93aWRlCmBgYAoKSGllciB3aXJkIGhpZXIgZWluIElCQ0YgcmVjb21tZW5kZXIgZ2ViYXV0LCB1bSBkaWUgY29zaW5lIHNpbWlsYXJpdHkgTWF0cml4IGRlciBGaWxtZSBtaXRoaWxmZSB2b24gUmVjb21tZW5kZXJsYWIgenUgZXJzdGVsbGVuLiBEYWJlaSB3dXJkZW4gZm9sZ2VuZGUgUGFyYW1ldGVyIGVpbmdlc3RlbGx0OgotIGs6IGluIFJlY29tbWVuZGVybGFiIHdpcmQgZGllIHNpbWlsYXJpdHkgenUgayBOYWNoYmFyZW4gYmVyZWNobmV0LiBEYW1pdCBkaWUgSW1wbGVtZW50aWVydW5nIG1pdCBkZXIgRWlnZW5lbiDDvGJlcmVpbiBzdGltbWVuIGthbm4sIG11c3MgZGllc2VyIFdlcnQgZ2xlaWNoIGdyb3NzIG9kZXIgZ3LDtnNzZXIgYWxzIGRpZSAgQW56YWhsIEl0ZW1zIGluIGRlbiBEYXRlbiBzZWluLiBEYSB3aXIgMTAwIEZpbG1lIGF1c2dld8OkaGx0IGhhYmVuLCB3aXJkIGs9MTAwIGdld8OkaGx0LgoKLSBub3JtYWxpemU6IFJlY29tbWVuZGVybGFiIG5vcm1hbGlzaWVydCBkaWUgUmF0aW5ncyBzdGFuZGFyZG3DpHNzaWcuIERhbWl0IGRpZXMgbWl0IGRlciBlaWdlbmVuIEltcGxlbWVudGllcnVuZyDDvGJlcmVpbiBzdGltbXQsIHdpcmQgZGllIE5vcm1hbGlzaWVydW5nIGhpZXIgZGVha3RpdmllcnQuCgotIG5hX2FzX3plcm86IE5BJ3Mgd2VyZGVuIGltIFJlY29tbWVuZGVyIEJlcmVjaG51bmcgc3RhbmRhcmRtw6Rzc2lnIGF1c2dlbGFzc2VuLiBEYSBpbiBkZXIgZWlnZW5lbiBJbWVwbGVudGllcnVuZyBkaWUgTkEncyBhdWNoIGF1ZiAwIGdlc2V0enQgd3VyZGVuLCB3dXJkZSBkaWVzIGhpZXIgYXVjaCBnZW1hY2h0LiBIw6R0dGUgbm9jaCBlaW5lIE5vcm1hbGlzaWVydW5nIHN0YXR0Z2VmdW5kZW4sIHfDpHJlIGRpZXMgYmVpc3BpZWxzd2Vpc2UgYmVpIG5vcm1hbGl6ZT0nY2VudGVyJyBkZW4gTWl0dGVsd2VydC4gCgoKYGBge3J9CmtfdmFsdWUgPSBkaW0oc2FtcGxlX3NpbV9yYXRpbmcpWzJdCnByaW50KHBhc3RlKCJLLVdlcnQ6ICIsIGtfdmFsdWUpKQoKc3RhcnQudGltZSA8LSBTeXMudGltZSgpCnJlYyA8LSBSZWNvbW1lbmRlcihzYW1wbGVfc2ltX3JhdGluZywgbWV0aG9kID0gIklCQ0YiLCBwYXJhbT1saXN0KG1ldGhvZD0iQ29zaW5lIiwgaz1rX3ZhbHVlLCBub3JtYWxpemUgPSBOVUxMLCBuYV9hc196ZXJvID0gVFJVRSkpCmVuZC50aW1lIDwtIFN5cy50aW1lKCkKZWxhcHNlZC50aW1lIDwtIHJvdW5kKChlbmQudGltZSAtIHN0YXJ0LnRpbWUpLCAzKQpwcmludChlbGFwc2VkLnRpbWUpCgpzaW1pbGFyaXR5IDwtIGFzLm1hdHJpeChyZWNAbW9kZWwkc2ltKQojaW1hZ2Uoc2ltaWxhcml0eSkKcGxvdF9zaW0oc2ltaWxhcml0eSkKCmBgYApFcyB3aXJkIHNpY2h0YmFyLCBkYXNzIGRpZSBEaWFnb25hbHdlcnRlIGVpbmUgYW5kZXJlIEZhcmJlIGF1ZndlaXNlbi4gTGVpZGVyIGthbm4gbWFuIGRpZSBTaW1pbGFyaXRpZXMgYXVmZ3J1bmQgZGVyIE1lbmdlIHZvbiBEYXRlbnB1bmt0ZW4gbmljaHQgd2lya2xpY2ggdmVyZ2xlaWNoZW4uIFdlcmRlbiBkaWUgZXJzdGVuIFdlcnRlIHZpc3VhbGlzaWVydCwgd2lyZCBqZWRvY2gga2xhciBkYXNzIGRpZSBEaWFnb25hbGVpbnRyw6RnZSAwIGFuc3RhdHQgMSBzaW5kLiBEaWVzIGlzdCBqZWRvY2ggbmljaHQgd2VpdGVyIHRyYWdpc2NoLCBkYSBkaWVzZSBEYXRlbiBrZWluZSBJbmZvcm1hdGlvbmVuIHRyYWdlbi4gU2llIGvDtm5uZW4gZGVzaGFsYiBpZ25vcmllcnQgd2VyZGVuLgoKYGBge3J9CnNpbWlsYXJpdHlbMTozLCAxOjNdCmBgYAoKYGBge3J9CgojIHNvcnQgY29sdW1zIGFscGhhYmV0aWNhbCB3aXRob3V0IHVzZXIgY29sdW1uIGluZGV4ZXMKc2FtcGxlX3NpbV96ZXJvIDwtIHNhbXBsZV9zaW1fd2lkZVstMV1bLCBvcmRlcihjb2xuYW1lcyhzYW1wbGVfc2ltX3dpZGVbLTFdKSksXQojIGNvbnZlcnQgdG8gbWF0cml4CnNhbXBsZV9zaW1femVybyA8LSBhcyhzYW1wbGVfc2ltX3plcm8sICdtYXRyaXgnKQojIHJlcGxhY2UgbmFzIHdpdGggMCAobm9uIGFkanVzdGVkIGNvc2luZSBzaW1pbGFyaXR5KQpzYW1wbGVfc2ltX3plcm9baXMubmEoc2FtcGxlX3NpbV96ZXJvKV0gPC0gMAoKc3RhcnQudGltZSA8LSBTeXMudGltZSgpCmNvc2luZV9zaW1fbWF0cml4IDwtIGNvc2luZV9zaW0yKHQoc2FtcGxlX3NpbV96ZXJvKSwgdChzYW1wbGVfc2ltX3plcm8pKQplbmQudGltZSA8LSBTeXMudGltZSgpCmVsYXBzZWQudGltZSA8LSByb3VuZCgoZW5kLnRpbWUgLSBzdGFydC50aW1lKSwgMykKcHJpbnQoZWxhcHNlZC50aW1lKQoKcGxvdF9zaW0oY29zaW5lX3NpbV9tYXRyaXgpCgpgYGAKCkhpZXIgd3VyZGUgZGllIGNvc2luZSBzaW1pbGFyaXR5IGFscyBNYXRyaXggQmVyZWNobnVuZyBpbXBsZW1lbnRpZXJ0LiBEZXIgWmVpdGF1ZndhbmQgZGVyIEJlcmVjaG51bmcgaXN0IGV0d2FzIGdlcmluZ2VyIGFscyBiZWkgZGVyIEltcGxlbWVudGllcnVuZyB2b24gUmVjb21tZW5kZXJsYWIuIERpZXMgaXN0IGRlciBGYWxsLCBkYSBpbSByZWNvbW1lbmRlcmxhYiBQYWNrYWdlIG5vY2ggd2VpdGVyZSBTY2hyaXR0ZSBkdXJjaGxhdWZlbiB3ZXJkZW4sIHVtIGJlaXNwaWVsc3dlaXNlIGbDvHIgayBOYWNoYmFyZW4genUgb3B0aW1pZXJlbi4KV2llIG1hbiBlcmtlbm5lbiBrYW5uLCBzaW5kIGRpZSBBdXNwcsOkZ3VuZ2VuIGRlciBTaW1pbGFyaXRpZXMgw6RobmxpY2ggenVyIFJlY29tbWVuZGVybGFiIEltcGxlbWVudGllcnVuZywgYmlzIGF1ZiBkaWUgRGlhZ29uYWx3ZXJ0ZS4gRGllc2Ugd2VyZGVuIGRlc2hhbGIgbm9jaCBkdXJjaCAwIGVyc2V0enQuCgpgYGB7cn0KZGlhZyhjb3NpbmVfc2ltX21hdHJpeCkgPC0gMApjb3NpbmVfc2ltX21hdHJpeFsxOjMsIDE6M10KYGBgCkF1Y2ggZGllIGVyc3RlbiBaYWhsZW53ZXJ0ZSBzdGltbWVuIG1pdCBkZW0gUHJpbnQgZGVyIHNpbWlsYXJpdGllcyB2b24gcmVjb21tZW5kZXJsYWIgw7xiZXJlaW4uCgoKTnVuIHdlcmRlbiBkaWUgWmFobGVud2VydGUgZGVyIHp3ZWkgYmVyZWNobmV0ZW4gc2ltaWxhcml0eSBNYXRyaXplbiB2ZXJnbGljaGVuLgpgYGB7cn0Kc3VtKGFicyhjb3NpbmVfc2ltX21hdHJpeCAtIHNpbWlsYXJpdHkpKQpgYGAKCldpZSBoaWVyIHNpY2h0YmFyIHdpcmQsIGlzdCBkaWUgU3VtbWUgZGVyIGFic29sdXRlbiBEaWZmZXJlbnplbiBhbGxlciBXZXJ0ZSBkZXIgTWF0cml6ZW4gdmVyc2Nod2luZGVuZCBrbGVpbi4gRGllIE1hdHJpemVuIHNpbmQgYWxzbyBiaXMgYXVmIGRlbiBGbGllc3Nrb21tYWZlaGxlciBpZGVudGlzY2guCgoKQWxzIG7DpGNoc3RlcyB3aXJkIGRpZSBqYWNjYXJkIHNpbWlsYXJpdHkgYmVyZWNobmV0LiBEYWbDvHIgd2VyZGVuIGRpZSBSYXRpbmdzIHp1ZXJzdCBiaW7DpHJpc2llcnQuIEFscyBTcGxpdGtyaXRlcml1bSB3dXJkZSBlaW4gUmF0aW5nIHZvbiAzIGdld8OkaGx0LCB3YXMgYmVkZXV0ZXQgZGFzcyBhbGxlIFJhdGluZ3MgYWIgMyBhbHMgVHJ1ZSBkYXJnZXN0ZWxsdCB3ZXJkZW4sIGFsbGUgUmF0aW5ncyBkYXJ1bnRlciBhbHMgRmFsc2UuCgoKYGBge3J9CiMgYmluYXJpemUgbWF0cml4IGFuZCBtYWtlIHNwbGl0IGF0IGEgcmF0aW5nIG9mIDMKc2FtcGxlX3NpbV9iaW4gPC0gYXMoYmluYXJpemUoYXMoc2FtcGxlX3NpbV9yYXRpbmcsICJyZWFsUmF0aW5nTWF0cml4IiksIG1pblJhdGluZz0zKSwgIm1hdHJpeCIpICogMQoKIyByZXBsYWNlIG5hcyB3aXRoIDAgKG5vIGFkanVzdGVkIGNvc2luZSBzaW1pbGFyaXR5KQojd2lkZV9tYXRyaXhbaXMubmEod2lkZV9tYXRyaXgpXSA8LSAwCgojIGliY2YsIGJlY2F1c2UgY29sdW1ucyBhcmUgdGFrZW4gaGVyZQojIHJvdyBjb3VudAoKc3RhcnQudGltZSA8LSBTeXMudGltZSgpCmphY19vd24gPC0gamFjY2FyZF9zaW0yKHQoc2FtcGxlX3NpbV9iaW4pLCB0KHNhbXBsZV9zaW1fYmluKSkKZW5kLnRpbWUgPC0gU3lzLnRpbWUoKQplbGFwc2VkLnRpbWUgPC0gcm91bmQoKGVuZC50aW1lIC0gc3RhcnQudGltZSksIDMpCnByaW50KGVsYXBzZWQudGltZSkKCnBsb3Rfc2ltKGphY19vd24pCgojZGltKHdpZGVfbWF0cml4KQoKYGBgCgpgYGB7cn0KamFjX293blsxOjMsIDE6M10KYGBgCgpBdWNoIGJlaSBkZXIgSW1wbGVtZW50aWVydW5nIGRlciBKYWNjYXJkIFNpbWlsYXJpdHkgaXN0IGRhbmsgTWF0cml4aW1wbGVtZW50YXRpb24gZGVyIFplaXRhdWZ3YW5kIHJlbGF0aXYgZ2VyaW5nLgpIaWVyIGbDpGxsdCBqZWRvY2ggYXVmLCBkYXNzIGF1ZiBkZXIgRGlhZ29uYWxlbiBMw7xja2VuIGJlc3RlaGVuLgoKCmBgYHtyfQpwcmludChwYXN0ZSgiTkEgdmFsdWUgY291bnQgaW4gc2ltaWxhcml0eSBtYXRyaXg6Iiwgc3VtKGlzLm5hKGphY19vd24pKSkpCmphY19vd25bNDM6NDUsIDQzOjQ1XQpqYWNfb3duWzM4OjQwLCAzODo0MF0KYGBgCgoKYGBge3J9CnByaW50KHBhc3RlKHN1bShzYW1wbGVfc2ltX2JpblssNDRdKSwgInBlb3BsZSBoYXZlIHJhdGVkIDxIb21hZ2UgKDE5OTUpPiAzIG9yIGhpZ2hlci4iKSkKcHJpbnQocGFzdGUoc3VtKHNhbXBsZV9zaW1fYmluWywzOV0pLCAicGVvcGxlIGhhdmUgcmF0ZWQgPEdvcmR5ICgxOTk1KT4gMyBvciBoaWdoZXIuIikpCmBgYApCZWkgRHVyY2hzdWNodW5nIGRlcyBEYXRlbnNhdHplcyBpc3QgYXVmZmFsbGVuZCwgZGFzcyBkaWVzZSBGaWxtZSBudXIgbmFnYXRpdmUgQmV3ZXJ0dW5nZW4gZW50aGFsdGVuLiBEdXJjaCBkaWUgSW1wbGVtZW50aWVydW5nIGRlciBKYWNjYXJkIFNpbWlsYXJpdHkgZW50c3RlaHQgZGFkdXJjaCBpbSBOZW5uZXIgZWluZSAwLCB3YXMgenUgZWluZXIgamFjY2FyZCBzaW1pbGFyaXR5IHZvbiBOQSBmw7xocnQuCgpBbHMgTsOkY2hzdGVzIHdpcmQgZGllIG5vcm1pZXJ0ZSBDb3NpbmUgw4RobmxpY2hrZWl0c21hdHJpeCBiZXJlY2huZXQuCgoKYGBge3J9Cm1lYW5fdG90YWwgPC0gbWVhbihzYW1wbGVfc2ltX3dpZGVfbm9ybSwgbmEucm09VFJVRSkKCmZvcihjb2xfaSBpbiAxOmRpbShzYW1wbGVfc2ltX3dpZGVfbm9ybSlbMl0pCnsKICAjIHJlcGxhY2UgbmFzIHdpdGggMCAobm9uIGFkanVzdGVkIGNvc2luZSBzaW1pbGFyaXR5KQogIG1lYW5fY29sID0gbWVhbihzYW1wbGVfc2ltX3dpZGVfbm9ybVssY29sX2ldLCBuYS5ybT1UUlVFKQogICNwcmludChtZWFuX2NvbCkKICBzYW1wbGVfc2ltX3dpZGVfbm9ybVtpcy5uYShzYW1wbGVfc2ltX3dpZGVfbm9ybVssY29sX2ldKSwgY29sX2ldIDwtIG1lYW5fY29sCgp9CgpzdGFydC50aW1lIDwtIFN5cy50aW1lKCkKY29zaW5lX3NpbV9ub3JtIDwtIGNvc2luZV9zaW0yKHQoc2FtcGxlX3NpbV93aWRlX25vcm0pLCB0KHNhbXBsZV9zaW1fd2lkZV9ub3JtKSkKZW5kLnRpbWUgPC0gU3lzLnRpbWUoKQplbGFwc2VkLnRpbWUgPC0gcm91bmQoKGVuZC50aW1lIC0gc3RhcnQudGltZSksIDMpCnByaW50KGVsYXBzZWQudGltZSkKCnBsb3Rfc2ltKGNvc2luZV9zaW1fbm9ybSkKCmBgYAoKSW4gZGllc2VyIERhcnN0ZWxsdW5nIGlzdCBkaWUgbm9ybWllcnRlIGNvc2luZSBzaW1pbGFyaXR5IGRhcmdlc3RlbGx0LiBGw7xyIGRpZSBOb3JtaWVydW5nIHd1cmRlIG1pbi1tYXggTm9ybWFpbGlzaWVydW5nIGdld8OkaGx0LCBtaXQgZGVtIE1pdHRlbHdlcnQgZGVyIHJhdGluZ3MgcHJvIEZpbG0gYWxzIE5BIEVyc2F0ei4gRGFkdXJjaCBlbnRzdGVodCB3aWUgZXJ3YXJ0ZXQgZ3J1bmRzw6R0emxpY2ggZWluZSBow7ZoZXJlIHNpbWlsYXJpdHksIHdlc3NlbiBXZXJ0ZSBzaWNoIHp3aXNjaGVuIDAgdW5kIDEgYW5zaWVkZWxuLgoKYGBge3IgZmlnLndpZHRoID0gMTUsIGZpZy5oZWlnaHQgPSA1fQpwMSA8LSBwbG90X3NpbShjb3NpbmVfc2ltX21hdHJpeCkKcDIgPC0gcGxvdF9zaW0oamFjX293bikKcDMgPC0gcGxvdF9zaW0oY29zaW5lX3NpbV9ub3JtKQoKZ3JpZC5hcnJhbmdlKHAxLCBwMiwgcDMsIG5jb2wgPSAzLCBucm93ID0gMSkKYGBgCgpEaWUgdW5ub3JtYWxpc2llcnRlbiBDb3NpbmUgdW5kIEphY2NhcmQgw4RobmxpY2hrZWl0c21hdHJpemVuIHNpbmQgc2ljaCBzZWhyIMOkaG5saWNoLiBTaWUgd2Vpc2VuIMOkaG5saWNoZSBzdHJ1a3R1cmVsbGUgRWlnZW5zY2hhZnRlbiBhdWYuIERpZSBKYWNjYXJkIMOEaG5saWNoa2VpdHNtYXRyaXggZW50aMOkbHQgZ2VuZXJlbGwgZXR3YXMgdGllZmVyZSBXZXJ0ZSB1bmQgaXN0IGRlc2hhbGIgaGVsbGVyLiBFcyB3ZXJkZW4gamVkb2NoIGVpbnplbG5lIFB1bmt0ZSBzaWNoYmFyLCB3ZWxjaGUgZWluZSDDhGhubGljaGtlaXQgdm9uIDEgYXVmd2Vpc2VuLiAKCgpgYGB7cn0KcHJpbnQoamFjX293blsyNToyOCwgMjU6MjddKQpwcmludChzYW1wbGVfc2ltX3dpZGVbLCdEZXNpZ25hdGVkIE1vdXJuZXIsIFRoZSAoMTk5NyknXSAlPiUgZHJvcF9uYSgpKQpwcmludChzYW1wbGVfc2ltX3dpZGVbLCdEYWRldG93biAoMTk5NSknXSAlPiUgZHJvcF9uYSgpKQpgYGAKVE9ETzoga2xhcmVyZSBkYXJzdGVsbHVuZyBldnRsPwoKRGllcyBpc3QgYmVpc3BpZWxzd2Vpc2UgYmVpIGRlbiBGaWxtZW4gJ0Rlc2lnbmF0ZWQgTW91cm5lciwgVGhlICgxOTk3KScgdW5kICdEYWRldG93biAoMTk5NSknIGRlciBGYWxsLiBEaWVzZSBGaWxtZSB3dXJkZSBkcmVpLCBiencuIGVpbiBNYWwgYmV3ZXJ0ZXQuIERlciBSZXN0IGRlciBXZXJ0ZSBpc3QgamV3ZWlscyBhdWYgMCBnZXNldHp0LiBEZXNoYWxiIHdpcmQgZGllIENvc2luZSDDhGhubGljaGtlaXQgendpc2NoZW4gZGllc2VuIFdlcnRlbiBrYXVtIGVpbmUgQXVzc2FnZSB0cmVmZmVuIGvDtm5uZW4uIERpZXNlIFdlcnRlIHNpbmQgZGVzaGFsYiB2b24gbmllZHJpZ2VyIEJlZGV1dHVuZy4KCgpEaWUgbm9ybWFsaXNpZXJ0ZSBDb3NpbmUgw4RobmxpY2hrZWl0c21hdHJpeCBpc3QgZXR3YXMgYW5kZXJzIGluIGRlciBTdHJ1a3R1ci4gRGFkdXJjaCwgZGFzcyBkaWUgTWl0dGVsd2VydGUgZGVyIGpld2VpbGlnZW4gRmlsbWJld2VydHVuZ2VuIGR1cmNoIGRpZSBmZWhsZW5kZW4gRGF0ZW4gZWluIGhvaGVzIEdld2ljaHQgYXVmIGRpZSBEYXRlbiBoYWJlbiwgZW50c3RlaGVuIGdlbmVyZWxsIGdyw7Zzc2VyZSBBYnN0w6RuZGUgendpc2NoZW4gZGVuIEJld2VydHVuZ2VuIGVpbnplbG5lciBGaWxtZS4gRGllc2Ugd2VyZGVuIHNpY2h0YmFyIGR1cmNoIFN0cmVpZmVuLiBEYWR1cmNoIGxpZWd0IGVpbiBzdMOkcmtlcmVyIEZva3VzIGF1ZiBkZW4gVW50ZXJzY2hpZWRlbiBkZXIgRmlsbWJld2VydHVuZ2VuIGltIEFsbGdlbWVpbmVuIHVuZCB3ZW5pZ2VyIGF1ZiBkZW4gVW50ZXJzY2hpZWRlbiBlaW56ZWxuZXIgUmF0aW5ncy4KRGFkdXJjaCB2ZXJzY2h3aW5kZW4gZGllIHNpbWlsYXJpdGllcyBlaW56ZWxuZXIgRmlsbWUgZWluIHdlbmlnIHVuZCBkaWUgR3JhZmlrIGlzdCBzY2h3ZXJlciB6dSBsZXNlbi4gV8OkcmUgZGllIE1hdHJpeCB3ZW5pZ2VyIHNwYXJjZSwgd8O8cmRlIGRpZXNlIEltcHVhdGlvbiBuaWNodCBzbyBzdGFyayBpbnMgR2V3aWNodCBmYWxsZW4gdW5kIGRpZSBEYXJzdGVsbHVuZyBrw7ZubnRlIGJlc3NlciBhYmdlbGVzZW4gd2VyZGVuLiBJbiBkaWVzZW0gRmFsbGUgaXN0IGRpZXNlIEdyYWZpayBqZWRvY2ggbmljaHQgZ3V0IGdlZWlnbmV0LgoKKioqCiMjIEltcGxlbWVudGllcnVuZyBUb3AtTiBNZXRyaWtlbgojIyMjIENhdGFsb2cgY292ZXJhZ2UgYW5kIFN5c3RlbS1sZXZlbCBub3ZlbHR5CmBgYHtyfQpyZWMgPC0gUmVjb21tZW5kZXIodHJhaW4sIG1ldGhvZCA9ICJJQkNGIiwgcGFyYW09bGlzdChtZXRob2Q9IkNvc2luZSIsIGs9MzAsIG5vcm1hbGl6ZSA9IE5VTEwsIG5hX2FzX3plcm8gPSBUUlVFKSkgI25vcm1hbGl6ZSA9ICdjZW50ZXInLCAnWi1zY29yZScKCmRmX2NvdmVyYWdlIDwtIHNob3dfY292ZXJhZ2UoYyg1LDEwLDE1LDIwLDI1LDMwKSwgcmVjKQpkZl9ub3ZlbHR5IDwtIHNob3dfbm92ZWx0eShjKDUsMTAsMTUsMjAsMjUsMzApKQoKZGZfY29tYmluZWQgPC0gaW5uZXJfam9pbihkZl9jb3ZlcmFnZSwgZGZfbm92ZWx0eSwgYnkgPSAnTicpCmBgYApDb3ZlcmFnZTogU3VtbWUgYWxsZXIgdW50ZXJzY2hpZWRsaWNoZW4gUHJvZHVrdGUsIHdlbGNoZSBpbiBkZW4gVG9wLU4gTGlzdGVuIGFsbGVyIEt1bmQqSW5uZW4gaW5zZ2VzYW10IGF1ZnRhdWNoZW4gZGl2aWRpZXJ0IGR1cmNoIGRpZSBNZW5nZSBhbGxlciBQcm9kdWt0ZS4KTm92ZWx0eTogTWl0dGVsIGRlciBTaGFubm9uIEluZm9ybWF0aW9uIGRlciBQb3B1bGFyaXTDpHQgZGVyIFByb2R1a3RlIGluIGRlciBUb3AtTiBMaXN0ZSBnZW1pdHRlbHQgw7xiZXIgYWxsZSBLdW5kKklubmVuLiAKCmBgYHtyfQpnZ3Bsb3QoZGF0YT1kZl9jb21iaW5lZCwgYWVzKHg9Y292ZXJhZ2UsIHk9bm92ZWx0eSwgZ3JvdXA9MSkpICsKICBnZW9tX2xpbmUoKSArCiAgZ2VvbV90ZXh0KGFlcyhsYWJlbD1OKSwgdmp1c3Q9LS4yNSwgaGp1c3Q9LS4wNSwgc2hvdy5sZWdlbmQgPSBGQUxTRSkgKwogIGxhYnMoCiAgICB0aXRsZSA9ICJDb3ZlcmFnZSBnZWdlbsO8YmVyIE5vdmVsdHkgZsO8ciB2ZXJzY2hpZWRlbmUgTiIsCiAgICB5ID0gIk5vdmVsdHkiLAogICAgeCA9ICJDb3ZlcmFnZSIKICApICsKICB0aGVtZSh0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMikpCmBgYApUT0RPOiBkYXMgZ2FuemUgaW0gc2VsYmVuIHBsb3QgZsO8ciB2ZXJzY2hpZWRlbmUgcmVkdWt0aW9uZW4gZGFyc3RlbGxlbiArIHRleHQgKyB2ZXJzY2hpZWRlbmUgRGF0ZW5yZWR1a3Rpb25lbgoKKioqCiMjIEltcGxlbWVudGllcnVuZyBUb3AtTiBNb25pdG9yCiMjIyMgRml4aWVyZSAyMCB6dWbDpGxsaWcgZ2V3w6RobHRlIFRlc3RrdW5kZW4gZsO8ciBhbGxlIE1vZGVsbHZlcmdsZWljaGUKIyMjIyBCZXN0aW1tZSBkZW4gQW50ZWlsIGRlciBUb3AtTiBFbXBmZWhsdW5nIG5hY2ggR2VucmVzIHBybyBLdW5kZQoKVE9ETzogSGllciBhdWNoIDMgbWFsPyAtIG5laW4KVE9ETzogSUJDRiBpbSB0aXRlbCBlcnfDpGhuZW4KCmBgYHtyfQpyZWMgPC0gUmVjb21tZW5kZXIodHJhaW4sIG1ldGhvZCA9ICJJQkNGIiwgcGFyYW09bGlzdChtZXRob2Q9IkNvc2luZSIsIGs9MzAsIG5vcm1hbGl6ZSA9IE5VTEwsIG5hX2FzX3plcm8gPSBUUlVFKSkKZGZfdXNlcl9nZW5yZXNfdG9wX24gPC0gY3JlYXRlX2RmX3VzZXJfZ2VucmVzX3RvcF9uKHJlYywgZ2VucmVzKQpzaG93X2dlbnJlX2ZyYWN0aW9uX3Bsb3QoZGZfdXNlcl9nZW5yZXNfdG9wX24sIGRmX3VzZXJfZ2VucmVzX3RvcF9uJGNvdW50X3RvcF9uLCAiQW50ZWlsIEdlbnJlcyBpbiBUb3AtTiBFbXBmZWhsdW5nIHZvbiAyMCB6dWYuIEt1bmRlbiIpCmBgYApUT0RPOiB0ZXh0CgpBdWYgZGllc2VtIFBsb3QgaXN0IGRpZSBVbnRlcnNjaGllZGxpY2hlIFZlcnRlaWx1bmcgZGVyIEdlbnJlcyBpbiBkZW4gVG9wLU4gRW1wZmVobHVuZ2VuIGbDvHIgZGllIHZlcnNjaGllZGVuZW4gS3VuZGVuIHp1IHNlaGVuLiBFcyBmw6RsbHQgYXVmLCBkYXNzIGJlaSBkaWVzZW0gUmVjb21tZW5kZXIgZHVyY2hhdXMgdmVyc2NoaWVkZW5hcnRpZ2UgVmVydGVpbHVuZ2VuIGJlaSBkZW4gR2VucmVzIGbDvHIgZGllIHZlcnNjaGllZG5lbiBOdXR6ZXIgYXVmdHJldGVuLgoKIyMjIyBCZXN0aW1tZSBwcm8gS3VuZGUgZGVuIEFudGVpbCBuYWNoIEdlbnJlcyBzZWluZXIgVG9wLUZpbG1lICg9RmlsbWUsIHdlbGNoZSB2b20gS3VuZGVuIGRpZSBiZXN0ZW4gQmV3ZXJ0dW5nZW4gZXJoYWx0ZW4gaGFiZW4pCmBgYHtyfQpkZl91c2VyX2dlbnJlc19iZXN0IDwtIGNyZWF0ZV9kZl91c2VyX2dlbnJlc19iZXN0KG1vdmllcywgZGZfdXNlcl9nZW5yZXNfdG9wX24sIGdlbnJlcykKc2hvd19nZW5yZV9mcmFjdGlvbl9wbG90KGRmX3VzZXJfZ2VucmVzX2Jlc3QsIGRmX3VzZXJfZ2VucmVzX2Jlc3QkY291bnRfYmVzdCwgIkFudGVpbCBHZW5yZXMgZGVyIGJlc3RiZXdlcnRldGVuIEZpbG1lIHZvbiAyMCB6dWYuIEt1bmRlbiIpCmBgYApBdWYgZGllc2VtIFBsb3QgaXN0IGRpZSBVbnRlcnNjaGllZGxpY2hlIFZlcnRlaWx1bmcgZGVyIEdlbnJlcyBiZWkgZGVuIGJlc3RiZXdlcnRldGVuIEZpbG1lbiBmw7xyIGRpZSB2ZXJzY2hpZWRlbmVuIEt1bmRlbiB6dSBzZWhlbi4gQmVzdGJld2VydGV0IGJlZGV1dGV0IGluIGRpZXNlbSBGYWxsLCBkYXNzIGRpZSBCZXdlcnR1bmcgZWluZXMgRmlsbWVzIG1pbmRlc3RlbnMgMC41IGjDtmhlciBzZWluIG11c3MsIGFscyBkaWUgRHVyY2hzY2huaXR0bGljaGUgQmV3ZXJ0dW5nIGRlcyBOdXR6ZXJzLiBFcyBmw6RsbHQgYXVmLCBkYXNzIGJlaSBkZW4gVG9wLU4gRW1wZmVobHVuZ2VuIGFsbGdlbWVpbiBBY3Rpb24genUgd2VuaWcgZW1wZm9obGVuIHd1cmRlLiBDb21lZHkgaGluZ2VnZW4gd3VyZGUgaMOkdWZpZyB6dSB2aWVsIGVtcGZvaGxlbi4gQmVpIGdlbmF1ZXJlbSBiZXRyYWNodGVuIGbDpGxsdCBhdWYsIGRhc3MgZGllc2VyIFJlY29tbWVkZXIgYmVpc3BpZWxzd2Vpc2UgYmVpIEt1bmRlIE5yLiAzOCBhdWYgZGllIEdlbnJlcyBiZXpvZ2VuIHNlaHIgc2NobGVjaHRlIEVtcGZlaGx1bmdlbiBtYWNodC4KCiMjIyMgVmVyZ2xlaWNoZSBwcm8gS3VuZGUgVG9wLUVtcGZlaGx1bmdlbiB1bmQgVG9wLUZpbG1lbiBuYWNoIEdlbnJlcwpgYGB7ciBmaWcud2lkdGggPSA3LjUsIGZpZy5oZWlnaHQgPSA2fQpkZl91c2VyX2dlbnJlc19iZXN0IDwtIGNyZWF0ZV9kZl91c2VyX2dlbnJlc19iZXN0KG1vdmllcywgZGZfdXNlcl9nZW5yZXNfdG9wX24sIGdlbnJlcykKCnJlYyA8LSBSZWNvbW1lbmRlcih0cmFpbiwgbWV0aG9kID0gIklCQ0YiLCBwYXJhbT1saXN0KG1ldGhvZD0iQ29zaW5lIiwgaz0zMCwgbm9ybWFsaXplID0gTlVMTCwgbmFfYXNfemVybyA9IFRSVUUpKQpkZl91c2VyX2dlbnJlc190b3BfbiA8LSBjcmVhdGVfZGZfdXNlcl9nZW5yZXNfdG9wX24ocmVjLCBnZW5yZXMpCmRmX3VzZXJfZ2VucmVzIDwtIGNyZWF0ZV9kZl91c2VyX2dlbnJlcyhkZl91c2VyX2dlbnJlc190b3BfbiwgZGZfdXNlcl9nZW5yZXNfYmVzdCkKc2hvd19jbGV2ZWxhbmRfZG90X3Bsb3QoZGZfdXNlcl9nZW5yZXMsICdJQkNGIFJlY29tbWVuZGVyIG1pdCBDb3NpbmUgU2ltaWxhcml0eScpCmBgYApBdWYgZGllc2VtIFBsb3QgaXN0IGVyc2ljaHRsaWNoIHdlbGNoZSBHZW5yZXMgZGVyIElCQ0YgUmVjb21tZW5kZXIgbWl0IENvc2luZSBTaW1pbGFyaXR5IGbDvHIgZGllIDIwIEt1bmRlbiBlaGVyIHp1IHdlbmlnIG9kZXIgenUgdmllbCBlbXBmaWVobHQuIEJlaXNwaWVsc3dlaXNlIENvbWVkeSBtYWNodCBiZWkgZGVuIGJlc3RiZXdlcnRldGVuIEZpbG1lbiBpbSBEdXJjaHNjaG5pdHQgdW5nZWbDpGhyIDEyJSBhdXMsIGVyc2NoZWludCBpbiBkZW4gVG9wLU4gRW1wZmVobHVuZ2VuIGplZG9jaCB6dSBldHdhIDIxJS4KCmBgYHtyIGZpZy53aWR0aCA9IDcuNSwgZmlnLmhlaWdodCA9IDZ9CnJlYyA8LSBSZWNvbW1lbmRlcih0cmFpbiwgbWV0aG9kID0gIlVCQ0YiLCBwYXJhbT1saXN0KG1ldGhvZD0iSmFjY2FyZCIsIG5vcm1hbGl6ZSA9IE5VTEwpKQpkZl91c2VyX2dlbnJlc190b3BfbiA8LSBjcmVhdGVfZGZfdXNlcl9nZW5yZXNfdG9wX24ocmVjLCBnZW5yZXMpCmRmX3VzZXJfZ2VucmVzIDwtIGNyZWF0ZV9kZl91c2VyX2dlbnJlcyhkZl91c2VyX2dlbnJlc190b3BfbiwgZGZfdXNlcl9nZW5yZXNfYmVzdCkKc2hvd19jbGV2ZWxhbmRfZG90X3Bsb3QoZGZfdXNlcl9nZW5yZXMsICdVQkNGIFJlY29tbWVuZGVyIG1pdCBKYWNjYXJkIFNpbWlsYXJpdHknKQpgYGAKCmBgYHtyIGZpZy53aWR0aCA9IDcuNSwgZmlnLmhlaWdodCA9IDZ9CnJlYyA8LSBSZWNvbW1lbmRlcih0cmFpbiwgbWV0aG9kID0gIlBPUFVMQVIiKQpkZl91c2VyX2dlbnJlc190b3BfbiA8LSBjcmVhdGVfZGZfdXNlcl9nZW5yZXNfdG9wX24ocmVjLCBnZW5yZXMpCmRmX3VzZXJfZ2VucmVzIDwtIGNyZWF0ZV9kZl91c2VyX2dlbnJlcyhkZl91c2VyX2dlbnJlc190b3BfbiwgZGZfdXNlcl9nZW5yZXNfYmVzdCkKc2hvd19jbGV2ZWxhbmRfZG90X3Bsb3QoZGZfdXNlcl9nZW5yZXMsICdQb3B1bGFyIFJlY29tbWVuZGVyJykKYGBgCgpUT0RPOiBhZGQgcGxvdCBmb3Igc3ZkIHJlY29tbWVuZGVyCgojIyMjIERlZmluaWVyZSBlaW5lIFF1YWxpdMOkdHNtZXRyaWsgZsO8ciBUb3AtTiBMaXN0ZW4gdW5kIHRlc3RlIHNpZQpgYGB7cn0KCmFsZ29yaXRobXMgPC0gbGlzdCgKICAiSUJDRiBjb3NpbmUiID0gbGlzdChuYW1lPSJJQkNGIiwgcGFyYW09bGlzdChrID0gMzAsIG1ldGhvZCA9ICJjb3NpbmUiLCBub3JtYWxpemUgPSBOVUxMLCBuYV9hc196ZXJvID0gVFJVRSksIGRlc2MgPSAnSUJDRiBSZWNvbW1lbmRlciBtaXQgQ29zaW5lIFNpbWlsYXJpdHknKSwKICAiVUJDRiBKYWNjYXJkIiA9IGxpc3QobmFtZT0iVUJDRiIsIHBhcmFtPWxpc3QobWV0aG9kID0gImphY2NhcmQiKSwgZGVzYyA9ICdVQkNGIFJlY29tbWVuZGVyIG1pdCBKYWNjYXJkIFNpbWlsYXJpdHknKSwKICAiUG9wdWxhciIgPSBsaXN0KG5hbWU9IlBPUFVMQVIiLCBwYXJhbT1OVUxMLCBkZXNjID0gJ1BvcHVsYXIgUmVjb21tZW5kZXInKQopCgplcnJvcnMgPC0gdmVjdG9yKCkKYWxnb3MgPC0gdmVjdG9yKCkKZm9yIChhbGdvIGluIGFsZ29yaXRobXMpIHsKICByZWMgPC0gUmVjb21tZW5kZXIodHJhaW4sIG1ldGhvZCA9IGFsZ28kbmFtZSwgcGFyYW09YWxnbyRwYXJhbSkKICBkZl91c2VyX2dlbnJlc190b3BfbiA8LSBjcmVhdGVfZGZfdXNlcl9nZW5yZXNfdG9wX24ocmVjLCBnZW5yZXMpCiAgZGZfdXNlcl9nZW5yZXMgPC0gY3JlYXRlX2RmX3VzZXJfZ2VucmVzKGRmX3VzZXJfZ2VucmVzX3RvcF9uLCBkZl91c2VyX2dlbnJlc19iZXN0KQogIGVycm9yIDwtIGNvbXB1dGVfbWVhbl9hYnNvbHV0ZV9wZXJjZW50YWdlX2Vycm9yKGRmX3VzZXJfZ2VucmVzKQogIGFsZ29zIDwtIGMoYWxnb3MsIGFsZ28kZGVzYykKICBlcnJvcnMgPC0gYyhlcnJvcnMsIGVycm9yKQp9CgpkZl9lcnJvciA8LSBkYXRhLmZyYW1lKGRlc2NyaXB0aW9uID0gYWxnb3MsIGVycm9yID0gZXJyb3JzKQoKCmdncGxvdChkZl9lcnJvciwgYWVzKHg9ZGVzY3JpcHRpb24sIHkgPSBlcnJvcikpICsgCiAgZ2VvbV9jb2woZmlsbCA9ICdzdGVlbGJsdWUnKSArCiAgY29vcmRfZmxpcCgpICsKICBzY2FsZV95X2NvbnRpbnVvdXMoZXhwYW5kID0gYygwLDApKSArCiAgZ2VvbV90ZXh0KGFlcyhsYWJlbD1lcnJvciksIGhqdXN0PTEuNSwgY29sb3IgPSAnd2hpdGUnKSArCiAgbGFicygKICAgIHRpdGxlID0gIk1pdHRsZXJlciBhYnNvbHV0ZXIgcHJvemVudHVhbGVyIEZlaGxlciBkZXIgXG5HZW5yZS1BbnRlaWxlIGluIGRlbiBUb3AtTiBFbXBmZWhsdW5nZW4iLAogICAgeCA9IGVsZW1lbnRfYmxhbmsoKSwgCiAgICB5ID0gIk1pdHRsZXJlciBhYnNvbHV0ZXIgcHJvemVudHVhbGVyIEZlaGxlciIsCiAgICBmaWxsID0gZWxlbWVudF9ibGFuaygpCiAgKSArCiAgdGhlbWVfY2xhc3NpYygpICsgCiAgdGhlbWUoCiAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMiksCiAgICBsZWdlbmQucG9zaXRpb24gPSAnYm90dG9tJwogICkKYGBgCmFicyhkZjFfZHJhbWEgLSBkZjJfZHJhbWEpICsgYWJzKGRmMV9hY3Rpb25zIC0gZGYyX2FjdGlvbikgKyAuLi4KCgoK